评判算法的好坏

🙋如何评判一个算法的好坏呢？

回答：时间

10个数字

10万数字

实际运行的时间长多少？

不光要了解不同算法在运行时间上的区别，更重要的是根据数据输入量的大小，算法运行时间的变化趋势。

如何求运行时间

使用“步数”来描述运行时间。“1步”（就是指一个操作）就是计算的基本单位。

示例：对一堆乱序的数列进行排序

1. 从整个数列中寻找最小值
2. 将最小值和数列最左边的数字进行交换，回到步骤 1

计算步骤：

1. 如果数列中有 n 个数字，那么步骤 1 中“寻找最小值”的步骤只需要确认 n 个数字即可。

2. 将 “确认 1 个数字的大小” 作为操作的基本单位，需要时间 T_c ，那么步骤 1 的运行时间就是 n * T_c 。

3. “对两个数字进行交换” 也作为操作的基本单位，假设需要的时间为 T_s 。那么步骤 1 和步骤 2 总共重复 n 次，每经过 1 轮，需要查找的数字就减少 1 个，因此总的运行时间为：

   $$(n\times Tc + Ts)+((n-1)\times Tc + Ts)+((n-2)\times Tc + Ts)+ .... + (2\times Tc+Ts)+(1\times Tc+Ts)$$

   换算下来就是：

   $$\frac{1}{2}Tc\times n \times (n+1) + Ts \times n$$

   进一步换算：

   $$\frac{1}{2} \times Tc \times n^2 + (\frac{1}{2} \times Tc + Ts) \times n$$

运行时间表示法

Tc 和 Ts 都是基本单位，与输入无关。会根据输入变化而变化的只有数列的长度 n。

n 越大，上面式子中的 n² 也就越大，其他部分就相对变小了。也就是说，对式子影响最大的是 n²。

将结果表示称下面的形式：

O(n^2)所传达的信息：排序算法的运行时间与输入量 n 的平方成正比。

课堂练习

假设某个算法的运行时间为：

如何表达？

该算法使用大O表示法就可以表示为O(n^3)

如果某个算法的运行时间为：

如何表达？

使用大O表示法表示出来为O(nlogn)

这样的表示方法被称之为大 O 表示法。这里的 O 是来自于英语的 Order（表示“阶”的意思）

它最早由数学家 Paul Bachmann 于 1894 年引入，在计算机科学中被 Donald Knuth 在 1970 年代普及。该表示法用来描述一个函数的增长速率，其核心思想是描述一个算法在 最坏情况 下，输入数据量增加时，时间或空间需求的 增长趋势，也就是算法的 上界。

其他表示法

1. Ω 表示法（Big Omega Notation）：用于描述一个算法的 下界，算法在最好的情况下的一个增长趋势。
2. Θ 表示法（Big Theta Notation）：用于描述算法 精确增长的速率，也就是算法在最坏和最好的情况下的增长趋势相同。
3. o 表示法（Little o Notation）：用来表示一个算法的增长速度严格小于某个复杂度的增长，意味着算法的增长速度比给定函数增长得更慢。
4. ω 表示法（Little Omega Notation）：用来表示一个算法的增长速度严格大于某个复杂度的增长，意味着算法的增长速度至少比给定函数快。

在实际算法测量中，使用得最广泛的仍然是大O表示法。

复杂度

无论是时间复杂度还是空间复杂度，评判的都是一种 增长趋势。

1. 时间复杂度：算法执行所需的时间随着输入规模 n 增长的一个变化趋势。
2. 空间复杂度：算法执行所需的内存空间随着输入规模 n 增长的一个变化趋势。

-EOF-