「DSA」- 杂记

漫画:经典谷歌面试题“扔鸡蛋”,看看你会做吗?
https://mp.weixin.qq.com/s/NugGnNX4Vv3SNhQrmzjF-A

在近三天内修改的文章随机排序:MODIFY_DATE + RAND() * 4

算法复杂度(Algorithmic complexity)

什么是算法复杂度_icolakele的博客-CSDN博客_算法的复杂度

就是衡量程序执行效率的度量方法。衡量算法的好坏,不仅要看程序执行所需的时间,还要看程序用到的计算资源,比如内存资源。

事实上,算法复杂度包括时间复杂度(Time complexity)和空间复杂度(Space complexity)。我们平时说的算法复杂度,一般都是在说算法的时间复杂度。

时间复杂度

理论上讲,程序执行消耗的时间是无法事先估算的,那如何计算时间复杂度呢?换个思路,程序执行时必然有一定的步骤,不防假设执行每个步骤所需要的时间为t,t具体是什么值并不重要,然后只需要计算一个程序执行所需要的步骤,最终以步骤数来衡量算法时间复杂度。

理论上讲,程序执行消耗的时间是无法事先估算的,那如何计算时间复杂度呢?换个思路,程序执行时必然有一定的步骤,不防假设执行每个步骤所需要的时间为t,t具体是什么值并不重要,然后只需要计算一个程序执行所需要的步骤,最终以步骤数来衡量算法时间复杂度。

举个例子,计算1+2的复杂度是多少呢?

a = 1
b = 2
sum = a + b

一共有3个步骤,不防记作O(3),其实O(3) = O(1)。
计算正整数n的阶乘呢?

factorial = 1
for i = 1 to n
factorial = i * factorial

第一行执行1次,第二行执行n次 ,第三行执行n次,一共执行2n + 1次。不防记作O(2n + 1)。其实O(2n + 1) = O(n)。

大 O 表示法

现在可以很自然的引入大O表示法了(Big O notation)。为什么用O呢?其实这里的O源自短语函数的阶数(Order of the function)。
如果还记得高数中等价无穷小和等价无穷大的概念的话,就很容易理解大O表示法了。

f(x) = 3x3 + 2x +10

不难理解,当x趋于∞时,对f(x)值变化影响最大的是x³,那么我们就可以说f(x)和x³是等价无穷大的。因此,常数次执行步骤的算法复杂度统称为O(1),这也是为什么前面我说O(3) = O(1)。类似的,O(2n + 1) = O(n)。
计算算法时间复杂度时,我们只需要关心对结果影响最大的那一项,也就是直接找到计算结果等价无穷大最简洁的表示方法。因此我们可以推导出O(f(x)) = O(x³)。
大O表示法其实是在描述一个算法在遇到最糟糕的情况时执行的效率。
想象一下唐伯虎点秋香场景,从n个蒙面女生中点中秋香,最好的情况是第一次就点中秋香,最坏的情况则需要n次。这里,我们就认为找秋香的算法复杂度是O(n)。
有了以上的基础,我们就很容易理解下面这些常见的算法复杂度了。