编程在于折腾

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

计算机基础 算法分析 2016/01/19

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

算法分析符号及实例

算法分析符号

今天要为下学期的课程准备，打打酱油吧，感觉好多事要做啊啊啊啊啊。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 )
avatar high起来 😝
Android控件学习之ListView

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