编程在于折腾

算法分析符号和算法分析浅谈

本文于659天之前发表,文中内容可能已经过时。如有疑问,请在评论区留言。

算法分析符号及实例

算法分析符号

今天要为下学期的课程准备,打打酱油吧,感觉好多事要做啊啊啊啊啊。APP没有完成,JS也放下没有继续学习,就急急忙忙为下学期的《数据结构和算法》做准备,还有部门的官网任务,感觉这个假期是所有事情都不可能做好,哭。战线拉得太长了T-T

在看《算法导论》的时候,几个常见的算法分析符号把我难住了。(PS:讲的够快的,而且一堆定义,看到定义就头疼),经过百度后,略略能get到那个point,所以赶紧做笔记,以便以后温习,怕的是没几天就忘记了,白白浪费时间。

大O,Ω,Θ,主要用到的是这个符号,当然还有小o小Ω(类似w)。下面的描述是摘自pake007的博客

f (n) = O (g (n))代表g(n)是f(n)的一个上界,即f(n)的增长率小于等于(≤)g(n)的增长率,如n^2 = O(n^3),若f(n) = n^2, g(n) = 2n^2, 从而f(n) = O(g(n))也是正确的;

f (n) =Ω (g (n)) 代表g(n)是f(n)的一个下界,和O符号的意义正好相反,代表f(n)的增长率大于等于(≥)g(n)的增长率;

f (n) = Θ(g (n)) 代表两个函数以相同的速率增长,若f(n) = 2n^2,则写成f(n) = Θ(n^2)是最好的答案;

f (n) = o (g (n)) 和大O符号的意义基本相同,除了相等的情况外,即表示f(n)的增长率小于(<)g(n)的增长率.

由理可得,小Ω代表f(n)的增长率大于(<)g(n)的增长率。

OK,看完之后有点眉目。但主要还是大O,Θ这两个经常搞混。再经过看视频和百度,Google,F(n) = Θ(g(n)) 等价于 F(n) = O(g(n)) AND F(n) = Ω(g(n)),并且在知乎发现了一张图,一图胜千言…所谓“增长率”和图中的“order”讲的是这个概念。

图片来自University of Manitoba CS3170算法分析课堂ppt

图片来自University of Manitoba CS3170算法分析课堂ppt

由图可以看出,大O是同阶或低阶,Θ是同阶。下面举几个例子。

n^2 = O(n3)—对的 n2 = Θ(n3)—错的 n2 = O(n2)—对的 n2 = Θ(n^2)—对的

为什么不讲Ω这个符号,其实在算法分析中很少会涉及到最优,很多时候考虑的是最坏的情况,而且,对算法的时间复杂度T(n),我们用符号大O来进行分析。

T(n):定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、……k次方阶O(n^k)。

实例

有了以上的概念,让我们看一些实例,一探究竟:来自学步园

O(n^2)

2.1. 交换i和j的内容

sum=0; (一次)

for(i=1;i<=n;i++) (n次 )

for(j=1;j<=n;j++) (n^2次 )

sum++; (n^2次 )

解:T(n)=2n^2+n+1 =O(n^2)
2.4.

i=1; ①

while (i<=n)

i=i*2; ②

解: 语句1的频度是1,

设语句2的频度是f(n), 则:2^f(n)<=n;f(n)<=log2n

取最大值f(n)= log2n,

T(n)=O(log2n )
Android控件学习之ListView

  1. 1. 算法分析符号及实例
    1. 1.1. 算法分析符号
    2. 1.2. 实例