• 大佬教程
• 菜鸟教程
• 程序笔记
• 保姆级教学！彻底学会时间复杂度和空间复杂度

def dogeggs_sum (n):
    sum = 0
    
    for dogegg in range(n):
        sum += dogegg
    return sum

大 O 表示法@H_519_197@

大 O 表示法࿰c;表示的是算法有多快。

这个多快࿰c;不是说算法代码真正的运行时间࿰c;而是代表着一种趋势࿰c;一种随着数据集的规模增大࿰c;算法代码运行时间变化的一种趋势。一般记作 Ｏ(f(n))。

那么之前的公式就变成 T(n) = O(f(n))࿰c;其中 f(n) 是算法代码执行的总步数࿰c;也叫操作数。

n 作为数据集大小࿰c;它可以取 1࿰c;10࿰c;100࿰c;1000 或者更大更大更大的数࿰c;到这你@R_452_10585@一件很有意思的事儿࿰c;那就是当数据集越来越大时࿰c;你会发现代码中的某些部分“失效”了。

还是以之前的代码为例。当 n = 1000 时࿰c;1 + 2n = 2001࿰c;当 n = 10000 时࿰c;1 + 2n = 20001࿰c;当这个 n 持续增大时࿰c;常数 1 和系数 2 对于最后的结果越来越没存在感࿰c;即对趋势的变化影响不大。

所以对于我们这段代码样例࿰c;最终的 T(n) = O(n)。

接下来再用两段代码进一步学一下求时间复杂度分析。

时间复杂度分析@H_519_197@

代码 1

def dogeggs_sum (n):
    sum = 0

    for dogegg in range(n):
        for i in range(n):
            sum += dogegg * i
    return sum

这段代码我会从最开始一点点带你来。

第 2 行需要运行 1 次 ࿰c;第 4 行需要运行 n 次࿰c;第 5 行和第 6 行分别需要运行 n² 次。所以总的运行次数 f(n) = 1 + n + 2n²。

当 n 为 5 的时候࿰c;f(n) = 1 + 5 + 2 * 25࿰c;当 n 为 10000 的时候࿰c;f(n) = 1 + 10000 + 2 * 100000000࿰c;当 n 更大呢？

这个时候其实很明显的就可以看出来 n² 起到了决定性的作用࿰c;像常数 1࿰c;一阶 n 和 系数 2 对最终的结果（即趋势）影响不大࿰c;所以我们可以把它们直接忽略掉࿰c;所以执行的总步数就可以看成是“主导”结果的那个࿰c;也就是 f(n) = n²。

自然代码的运行时间 T(n) = O(f(n)) = O(n²)。

代码 2

def dogeggs_sum (n):
    sum1 = 0
    for dogegg1 in range(n):
        sum1 += dogegg1

    sum2 = 0
    for dogegg2 in range(n):
        for i in range(n):
            sum2 += dogegg2 * i

    sum3 = 0
    for dogegg3 in range(n):
        for i in range(n):
            for j in range(n):
                sum3 += dogegg3 * i * j

    return sum1 + sum2 + sum3

上面这段代码是求三部分的和࿰c;经过之前的学习应该很容易知道࿰c;第一部分的时间复杂度是 O(n)࿰c;第二部分的时间复杂度是 O(n²)࿰c;第三部分是 O(n³)。

正常来讲࿰c;这段代码的 T(n) = O(n) + O(n²) + O(n³)࿰c;按照我们取“主导”部分࿰c;显然前面两个小弟都应该直接 pass࿰c;最终 T(n) = O(n³)。

通过这几个例子࿰c;聪明的小婊贝们肯定会发现࿰c;对于时间复杂度分析来说࿰c;只要找起“主导”作用的部分代码即可࿰c;这个主导就是最高的那个复杂度࿰c;也就是执行次数最多的那部分 n 的量级。

剩下的就是多加练习࿰c;有意识的多去想多去练࿰c;就可以和我一样 帅气 稳啦。

这里推荐两个比较好的资料࿰c;一份是笔记࿰c;一份最优解࿰c;两者加起来无敌。 两个月斩获 70k star࿰c;前字节大神刷题笔记 清华学霸的刷题笔记(leetcode最优解)

常见时间复杂度@H_519_197@

算法学习过程中࿰c;我们会遇到各种各样的时间复杂度࿰c;但纵使你代码七十二变࿰c;几乎也逃不过下面这几种常见的时间复杂度。

上表的时间复杂度由上往下依次增加࿰c;O(n) 和 O(n²) 前面已经讲过了࿰c;O(2n) 和 O(n!) 效率低到离谱࿰c;以后不幸碰到我再提一下࿰c;就不再赘述。

下面主要来看剩下几种最常见的时间复杂度。

O(1)

O(1) 是常数时间复杂度。

在这你要先明白一个概念࿰c;不是只执行 1 次的代码的时间复杂度记为 O(1)࿰c;只要你是常数࿰c;像 O(2)、O(3) … O(100000) 在复杂度的表示上都是 O(1)。

n = 10000
res = n / 2 
print(res)

比如像上面这段代码࿰c;它运行了 3 次࿰c;但是它的时间复杂度记为 O(1)࿰c;而不是 O(3)。

因为无论 n 等于多少࿰c;对于它们每行代码来说还是只是执行了一次࿰c;代码的执行时间不随 n 的变化而变化。

O(logn)

O(logn) 是对数时间复杂度。首先我们来看一段代码：

dogegg = 1

while dogegg < n:
    dogegg = dogegg * 2

根据之前讲的࿰c;我们先找“主导”࿰c;在这主导就是第 4 行代码࿰c;只要算出它的时间复杂度࿰c;总的时间复杂度就知道了。

其实很简单࿰c;上面的代码翻译一下就是初始化 dogegg = 1࿰c; 乘上多少个 2 以后会 ≥ n。

假设需要 x 个࿰c;那么相当于求：

即：

所以上述代码的时间复杂度应该为 O(log2n)。

但是对于对数复杂度来说࿰c;不管你是以 2、3 为底࿰c;还是以 10 为底࿰c;通通记作 O(logn)࿰c;这是为什么呢？

这就要从对数的换底公式说起。

根据换底公式࿰c;log2n 可以写成：

对于时间复杂度来说：

所以在对数时间复杂度中我们就忽略了底࿰c;直接用 O(logn) 来表示对数时间复杂度。

O(nlogn)

O(nlogn)࿰c;真的是很常见的时间复杂度࿰c;像后面会学到的快速排序、归并排序的时间复杂度都是 O(nlogn)。

如果只是简单看的话是在 logn 外面套了层 for 循环࿰c;比如像下面这段代码：

def stupid_cnt(n):
    cnt = 0
    for i in range(n):
        dogegg = 1

        while dogegg < n:
            dogegg = dogegg * 2
            cnt += 1
    return cnt

当然像上面这种 stupid 代码一般人不会写࿰c;我也只是举个例子给大家看࿰c;我是狗蛋࿰c;大家千万不要以为我是傻狗。

@H_673_30@