大家可移步算法分析——大O标记法进行对大O标记法进行了解；

目录

一. 理解不同的大O 运行时间

算法1

算法2

二. 大O 表示法指出了最糟情况下的运行时间

三. 一些常见的大O 运行时间

四. 确定大O表示法的原则

4.1 示例说明

1）忽略常数项

2）忽略低次项

3）忽略系数

4.2 示例练习：

4.3 示例代码

五. 总结

一. 理解不同的大O 运行时间

以一个你在家里使用纸和笔就能完成的实验来说明该问题。

假设你要画一个网格，它包含16个格子。

算法1

        一种方法是以每次画一个的方式画16个格子。记住，大O表示法计算的是操作数。在这个示例中，画一个格子是一次操作，需要画16个格子。如果每次画一个格子，需要执行多少次操作呢？

        画16个格子需要16步。这种算法的运行时间是多少？

答案：算法1的运行时间为O(n)；

算法2

        请尝试这种算法——将纸折起来。将纸对折一次就是一次操作。第一次对折相当于画了两个格子！再折，再折，再折。

        折4次后再打开，便得到了漂亮的网格！每折一次，格子数就翻倍，折4次就能得到16个格子！

        你每折一次，绘制出的格子数都翻倍，因此4步就能“绘制”出16个格子。这种算法的运行时间是多少呢？

答案：算法2的运行时间为O(log n)。

搞清楚这两种算法的运行时间之后，再继续。

二. 大O 表示法指出了最糟情况下的运行时间

        假设你使用简单查找在英文电话簿中找人。你知道，简单查找的运行时间为O(n)，这意味着在最糟情况下，必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人，一次就能找到，无需查看每个条目。考虑到一次就找到了Adit，请问这种算法的运行时间是O(n)还是O(1)呢？

简单查找的运行时间总是为O(n)。

        查找Adit时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

        除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。最糟情况和平均情况将在后面讨论。

三. 一些常见的大O 运行时间

        下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，这样的算法包括后面将介绍的快速排序——一种速度较快的排序算法。
• O(n2)，这样的算法包括后面将介绍的选择排序——一种速度较慢的排序算法。
• O(n!)，这样的算法包括后面将介绍的旅行商问题的解决方案——一种非常慢的算法。

        以上面绘制网格实验为例，且假设有5种不同的算法可供选择，这些算法的运行时间如上所示。

• 第一种算法，绘制该网格所需的操作数将为4（log 16 = 4）。假设你每秒可执行10次操作，那么绘制该网格需要0.4秒。如果要绘制一个包含1024格的网格呢？这需要执行10（log 1024 = 10）次操作，换言之，绘制这样的网格需要1秒。
• 第二种算法，其运行时间为O(n)。即要绘制16个格子，需要执行16次操作；要绘制1024个格子，需要执行1024次操作。执行这些操作需要多少秒呢？
• 整体如下图：

        还有其他的运行时间，但这5种是最常见的。

        这里做了简化，实际上，并不能如此干净利索地将大O运行时间转换为操作数，但就目前而言，这种准确度足够了。等继续学习其他一些算法后，将回过头来再次讨论大O表示法。当前，我们获得的主要启示如下：

• 算法的速度指的并非时间，而是操作数的增速。
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示。
• O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

四. 确定大O表示法的原则

        因此，大O表示法就是把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n2、n3等，原则如下：

• 如果运行时间是常数量级，则用常数1表示
• 只保留时间函数中的最高阶项
• 如果最高阶项存在，则省去最高阶项前面的系数

4.1 示例说明

1）忽略常数项

函数如下表：

函数增长图为：

        结论:

• 2n+20和 2n 随着n 变大，执行曲线无限接近, 20可以忽略
• 3n+10和 3n 随着n 变大，执行曲线无限接近, 10可以忽略

2）忽略低次项

函数如下表：

函数增长图为：

        结论:

• 2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
• n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20

3）忽略系数

函数如下表：

函数增长图为：

        结论:

• 随着n值变大，5n^2+7n和 3n^2 + 2n ，执行曲线重合, 说明这种情况下, 5和3可以忽略
• 而n^3+5n和 6n^3+4n，执行曲线分离，说明多少次方是关键

4.2 示例练习：

1) T(n) = 3n

T(n) = 3n
最高阶项为3n，省去系数3，则转化的时间复杂度为：T(n)=O(n)

2) T(n) = 5logn

T(n) = 5logn，
最高阶项为5logn，省去系数5，则转化的时间复杂度为：T(n) =O(logn)。

3) T(n) = 2

T(n) = 2，
只有常数量级，则转化的时间复杂度为：T(n) =O(1)。

4) T(n) = 0.5n2+ 0.5n

T(n) = 0.5n^2+ 0.5n，
最高阶项为0.5n^2，省去系数0.5，则转化的时间复杂度为：T(n) =O(n^2)。

        这4种时间复杂度究竟谁的程度执行用时更长，谁更节省时间呢？当n的取值足够大时，不难得出下面的结论：

        O(1))

public static int sum(int n) {
    int partialSum = 0;
    for(int i=1;i<=n;i++) {
        partialSum += i*i*i;
    }
    return partialSum;
}