各人好呀，我是帅蛋。
做为一名大学之前编程才能为零，认为计算机专业就是打游戏的咸鱼，到参与 ACM 竞赛，靠着划水和抱大腿拿了几块金银铜铁牌的前 ACM 混子选手，想起之前疯狂跪舔数据构造和算法的日子，至今我扔能掬出一把辛酸泪[流泪]
为了让各人不再像我如许当小我那么难，我决定和各人一路进修数据构造与算法，我希望能用傻瓜的体例，由浅入深，从概念到理论，一步一步的来，那个过程可能会很长，我希望在那个过程中你能喜好上它，能发现它们冰凉外表下有趣的灵魂。
今天来学复杂度阐发。
复杂度阐发次要就是时间复杂度和空间复杂度，接下来的文章也次要围绕那两方面来讲。废话不多说，前排马扎瓜子筹办好，帅蛋小课堂正式接客。
复杂度阐发刚刚我说过，在本蛋看来，复杂度阐发是数据构造和算法中最重要的常识点，毫不夸大的说，那就是数据构造与算法进修的核心所在。你学会了它你就入的了门，你学不会它，你就永久不晓得门儿在哪。
为什么复杂度阐发会那么重要？
那个就要从盘古开天辟地，呃，从数据构造与算法的自己说起。
我平常白日做梦的时候，老是想着当当咸鱼划划水就能赚大钱，更好就是能躺着，钱就间接砸到我脑阔上。数据构造与算法固然没有本蛋那么大的梦想，但是它的呈现也是想着花更少的时间和更少的存储来处理问题。
那若何去考量“更少的时间和更少的存储”，复杂度阐发为此而生。
帅蛋：所认为什么复杂度阐发重要你们晓得了叭？
臭宝：不晓得不晓得
帅蛋：啥？还不晓得？？？
臭宝：对呀对呀
帅蛋：。。。
既然你诚心诚意的不晓得，那我就大发慈善的打个不得当的例如。
若是把数据构造与算法看成武功招式，那复杂度阐发就是对应的心法。
若是只是学会了数据构造与算法的用法，不学复杂度阐发，那就和你费尽含辛茹苦在隔邻老王家次卧进门右手第二块地砖下偷挖出老王打遍村里无对手的村林至宝王霸拳，然后发现秘笈上只要招式，没有内功心法，好好得王霸拳变的还不如王八拳。只要学会了王霸之气，才气虎躯一震，王霸之气一噗，震走村口光棍李养的哈巴狗。
臭宝：哇，凶猛凶猛凶猛，你胖你说的都对，但仍是没需要学啊。
帅蛋：？？？
臭宝：如今有良多东西啊包啊，代码随意跑一下，就能悄悄松松晓得运行了几时间占了几内存啊。算法的效率不就轻松比对出来了么？
帅蛋：。。。
你们说的那种支流叫干事后统计法。
简单来说，就是你需要提早写好算法代码和编好测试数据，然后在计算机上跑，通过最初得出的运行时间判断算法时效的凹凸，那里的运行时间就是我们日常的时间。
我且不消“万一你费力心思写好的算法代码自己是个很蹩脚的解法”那种理由去辩驳你，过后统计法自己存在良多缺陷，它并非一个对我们来说有用的度量目标：
起首，过后统计法太依赖计算机的软件和硬件等性能。代码在 core i7 处置器的就比 core i5 处置器的运算速度快，更不消说差别的操做系统、差别的编程语言等软件方面，就算是在统一台电脑上，用的所有的工具都一样，内存的占用或者是 CPU 的利用率也会形成运行时间的差别。
再者，过后统计法太依赖于测试数据集的规模。同样是排序算法，你随意整 5 个 10 个的数排序，就算最垃圾的排序算法，也看起来快的和法拉利一样，若是是来10w 个 100w 个，那差别的算法的差距就很大了，并且同样是 10w 个 100w 个数，挨次和乱序的时间又差别了。
那么问题来了，到底测试数据集选几个适宜？数据的挨次若何定又算适宜？
说不出来了叭？
能够看出，我们需要一个不依赖于性能和规模等外力影响就能够预算算法效率、判断算法好坏的度量目标，而复杂度阐发生成就是干那个的，那也是为什么我们要进修并必需学会复杂度阐发！
时间复杂度时间复杂度，也就是指算法的运行时间。
关于某一问题的差别处理算法，运行时间越短算法效率越高，相反，运行时间越长，算法效率越低。
那么若何预算时间复杂度呢？
大佬们在拽掉脑阔上最初一根头发的时候发现，当用运行时间去描述一个算法快慢的时候，算法中施行的总步数显得尤为重要。
因为只是预算，我们能够假设每一行代码的运行时间都为一个 Btime，那么算法的总的运行时间 = 运行的总代码行数。
下面我们来看那么一段简单的代码。
def dogeggs_sum (n): sum = 0 for dogegg in range(n): sum += dogegg return sum在上面假设的情况下，那段求累加和的代码总的运行时间是几呢？
第 2 行代码需要 1 Btime 的运行时间，第 4 和 第 5行别离运行了 n 次，所以每个需要 n * Btime 的运行时间，所以总的运行时间就是 (1 + 2n) * Btime。
我们一般用 T 函数来暗示**赋值语句的总运行时间**，所以上面总的运行时间就能够表达成 T(n) = (1 + 2n) * Btime，翻译一下就是“数据集大小为 n，总步数为 (1 + 2n) 的算法的施行时间为 T(n)”。
通过公式，我们能够看出 T(n) 和总步数是成反比关系，那个规律的发现其实是很重要的，因为那个告诉了我们一种趋向，数据集规模和运行时间之间有趋向！
所有人筹办，我们很熟悉的大 O 闪亮退场了！
大 O 暗示法
大 O 暗示法，暗示的是算法有多快。
那个多快，不是说算法代码实正的运行时间，而是代表着一种趋向，一种跟着数据集的规模增大，算法代码运行时间变革的一种趋向。一般记做 Ｏ(f(n))。
那么之前的公式就酿成 T(n) = O(f(n))，此中 f(n) 是算法代码施行的总步数，也叫操做数。
n 做为数据集大小，它能够取 1，10，100，1000 或者更大更大更大的数，到那你就会发现一件很有意思的事儿，那就是当数据集越来越大时，你会发现代码中的某些部门“失效”了。
仍是以之前的代码为例。当 n = 1000 时，1 + 2n = 2001，当 n = 10000 时，1 + 2n = 20001，当那个 n 持续增大时，常数 1 和系数 2 关于最初的成果越来越没存在感，即对趋向的变革影响不大。
所以关于我们那段代码样例，最末的 T(n) = O(n)。
接下来再用两段代码进一步学一下求时间复杂度阐发。
时间复杂度阐发
代码 1
def dogeggs_sum (n): sum = 0 for dogegg in range(n): for i in range(n): sum += dogegg * i return sum那段代码我会从最起头一点点带你来。
第 2 行需要运行 1 次 ，第 4 行需要运行 n 次，第 5 行和第 6 行别离需要运行 n² 次。所以总的运行次数 f(n) = 1 + n + 2n²。
当 n 为 5 的时候，f(n) = 1 + 5 + 2 * 25，当 n 为 10000 的时候，f(n) = 1 + 10000 + 2 * 100000000，当 n 更大呢？
那个时候其实很明显的就能够看出来 n² 起到了决定性的感化，像常数 1，一阶 n 和 系数 2 对最末的成果（即趋向）影响不大，所以我们能够把它们间接忽略掉，所以施行的总步数就能够看成是“主导”成果的阿谁，也就是 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上面那段代码是求三部门的和，颠末之前的进修应该很容易晓得，第一部门的时间复杂度是 O(n)，第二部门的时间复杂度是 O(n²)，第三部门是 O(n³)。
一般来讲，那段代码的 T(n) = O(n) + O(n²) + O(n³)，根据我们取“主导”部门，显然前面两个小弟都应该间接 pass，最末 T(n) = O(n³)。
通过那几个例子，伶俐的小婊贝们必定会发现，关于时间复杂度阐发来说，只要找起“主导”感化的部门代码即可，那个主导就是更高的阿谁复杂度，也就是施行次数最多的那部门 n 的量级。
剩下的就是多加操练，有意识的多去想多去练，就能够和我一样 帅气 稳啦。
常见时间复杂度
算法进修过程中，我们会碰到各类各样的时间复杂度，但纵使你代码七十二变，几乎也逃不外下面那几种常见的时间复杂度。
时间复杂度
阶
f(n) 举例
常数复杂度
O(1)
1
对数复杂度
O(logn)
logn + 1
线性复杂度
O(n)
n + 1
线性对数复杂度
O(nlogn)
nlogn + 1
k 次复杂度
O(n²)、O(n³)、....
n² + n +1
指数复杂度
O(2n)
2n + 1
阶乘复杂度
O(n!)
n! + 1
上表的时间复杂度由上往下依次增加，O(n) 和 O(n²) 前面已经讲过了，O(2n) 和 O(n!) 效率低到离谱，以后不幸碰着我再提一下，就不再赘述。
下面次要来看剩下几种最常见的时间复杂度。
O(1)
O(1) 是常数时间复杂度。
在那你要先大白一个概念，不是只施行 1 次的代码的时间复杂度记为 O(1)，只要你是常数，像 O(2)、O(3) ... O(100000) 在复杂度的暗示上都是 O(1)。
n = 10000res = n / 2 PRint(res)好比像上面那段代码，它运行了 3 次，但是它的时间复杂度记为 O(1)，而不是 O(3)。
因为无论 n 等于几，关于它们每行代码来说仍是只是施行了一次，代码的施行时间不随 n 的变革而变革。
O(logn)
O(logn) 是对数时间复杂度。起首我们来看一段代码：
dogegg = 1while dogegg < n: dogegg = dogegg * 2按照之前讲的，我们先找“主导”，在那主导就是第 4 行代码，只要算出它的时间复杂度，总的时间复杂度就晓得了。
其实很简单，上面的代码翻译一下就是初始化 dogegg = 1， 乘上几个 2 以后会 ≥ n。
假设需要 x 个，那么相当于求：
即：
所以上述代码的时间复杂度应该为 O(log2n)。
但是关于对数复杂度来说，不管你是以 2、3 为底，仍是以 10 为底，统统记做 O(logn)，那是为什么呢？
那就要从对数的换底公式说起。
按照换底公式，log2n 能够写成：
关于时间复杂度来说：
所以在对数时间复杂度中我们就忽略了底，间接用 O(logn) 来暗示对数时间复杂度。
O(nlogn)
O(nlogn)，实的是很常见的时间复杂度，像后面会学到的快速排序、归并排序的时间复杂度都是 O(nlogn)。
若是只是简单看的话是在 logn 外面套了层 for 轮回，好比像下面那段代码：
def stupid_cnt(n): cnt = 0 for i in range(n): dogegg = 1 while dogegg < n: dogegg = dogegg * 2 cnt += 1 return cnt当然像上面那种 stupid 代码一般人不会写，我也只是举个例子给各人看，我是狗蛋，各人万万不要认为我是傻狗。
更好情况、最坏情况和均匀情况时间复杂度
除了数据集规模影响算法的运行时间外，“数据的详细情况”也会影响到运行时间。
我们来看那么一段代码：
def find_word(lst, word): flag = -1 for i in range(len(lst)): if lst[i] == word: flag = i break return flag上面那段简单代码是求变量 word 在列表 lst 中呈现的位置，我用那段来解释“数据的详细情况”是什么意思。
变量 word 可能呈现在列表 lst 的肆意位置，假设 a = ['a', 'b', 'c', 'd']：
当 word = 'a' 时，正好是列表 lst 的第 1 个，后面的不需要再遍历，那么本情况下的时间复杂度是 O(1)。当 word = 'd' 或者 word = 'e' 时，那两种情况是整个列表全数遍历完，那么那些情况下的时间复杂度是 O(n)。那就是数据的详细情况差别，代码的时间复杂度差别。
按照差别情况，我们有了更好情况时间复杂度、最坏情况时间复杂度和均匀情况时间复杂度那 3 个概念。
更好情况时间复杂度
更好情况就是在最抱负的情况下，代码的时间复杂度。对应上例变量 word 正好是列表 lst 的第 1 个，那个时候对应的时间复杂度 O(1) 就是那段代码的更好情况时间复杂度。
最坏情况时间复杂度
最坏情况就是在最差的情况下，代码的时间复杂度。对应上例变量 word 正好是列表 lst 的最初一个，或者 word 不存在于列表 lst，那个时候对应的时间复杂度 O(n) 是那段代码的最坏情况时间复杂度。
均匀情况时间复杂度
大大都情况下，代码的施行情况都是介于更好情况和最坏情况之间，所以又呈现了均匀情况时间复杂度。
那怎么计算均匀时间复杂度呢？那个说起来有点复杂，需要用到概率论的常识。
在那里我仍是用上面的例子来讲，因为只是简单的科普一下，为了便利计算，我假设的会有点随意：
从大的方面来看，查找变量 x 在列表 lst 中的位置有两种情况：在或者不在。假设变量 x 在或者不在列表 lst 中的概率都为 1/2。若是 x 在列表 lst 中，那么 x 有 n 种情况，它可能呈现在 0 到 n-1 中肆意位置，假设呈现在每个位置的概率都不异，都为 1/n。每个呈现的概率（即权重）晓得了，所以均匀时间复杂度为：
是不是看着有点眼熟，那就是我们都学过的加权均匀值。
什么，没学过？问题不大。加权均匀值就是将各数值乘以响应的权数，然后加总乞降得到总体值，再除以总的单元数。
所以最末的均匀时间复杂度就为：
臭宝：又是更好，又是最坏，又是均匀的，那么多到底用哪个呀？
蛋蛋：那个还用问？当然是选择最坏情况时间复杂度啊！
更好情况，反响最抱负的情况，怎么可能天上天天掉馅饼，没啥参考价值。
均匀情况，那却是能反映算法的全面情况，但是一般“全面”，就和什么都没说一样，也没啥参考价值。
最坏情况，干啥工作都要考虑最坏的成果，因为最坏的成果供给了一种保障，触底的保障，保障代码的运行时间那个就是最差的，不会有比它还差的。
所以，不需要纠结各类情况，算时间复杂度就算最坏的阿谁时间复杂度即可。
空间复杂度空间复杂度相较于时间复杂度来说，比力简单，需要掌握的内容不多。
空间复杂度和时间复杂度一样，反映的也是一种趋向，只不外那种趋向是代码运行过程中临时变量占用的内存空间。
臭宝：为什么是“临时”咧？
蛋蛋：那就要从代码在计算机中的运行说起啦。
代码在计算机中的运行所占用的存储空间呐，次要分为 3 部门：
代码自己所占用的输入数据所占用的临时变量所占用的前面两个部门是自己就要占那些空间，与代码的性能无关，所以我们在权衡代码的空间复杂度的时候，只关心运行过程中临时占用的内存空间。
空间复杂度记做 S(n)，暗示形式与时间复杂度一致。
在那同样 n 做为数据集大小，f(n) 指的是规模 n 所占存储空间的函数。
空间复杂度阐发
下面我们用一段简单代码来进修下若何阐发空间复杂度。
def dogeggs_sum(lst): sum = 0 for i in range(len(lst)): sum += lst[i] return sum上述代码是求列表 lst 的所有元素之和，按照之前说的，只计算临时变量所占用的内存空间。
形参 lst 所占的空间不计，那么剩下的临时变量只要 sum 和 i，sum 是存储和，是常数阶，i 是存储元素位置，也是常数阶，它俩所分配的空间和规模 n 都没有关系，所以整段代码的空间复杂度 S(n) = O(1)。
常见空间复杂度
常见的空间复杂度有 O(1)、O(n)、O(n²)，O(1) 在上节讲了，还有就是像 O(logn) 那种也有，但是等闲不会碰着，在那里就不罗嗦了。
O(n)
def create_lst(n): lst = [] for i in range(n): lst.apPEnd(i) return lst上面那段傻傻的代码有两个临时变量 lst 和 i。
此中 lst 是被创建的一个空列表，那个列表占用的内存跟着 for 轮回的增加而增加，更大到 n，所以 lst 的空间复杂度为 O(n)，i 是存储元素位置的常数阶，与规模 n 无关，所以那段代码最末的空间复杂度为 O(n)。
O(n²)
def create_lst(n): lst1 = [] for i in range(n): lst2 = [] for j in range(n): lst2.append(j) lst1.append(lst2) return lst1仍是一样的阐发体例，很明显上面那段傻二次方的代码创建了一个二维数组 lst，一维 lst1 占用 n，二维 lst2 占用 n²，所以最末那段代码的空间复杂度为 O(n²)。
到那里，复杂度阐发就全数讲完啦，只要臭宝们认实看完那篇文章，相信会对复杂度阐发有个根本的认识。复杂度阐发自己不难，只要多加操练，日常平凡写代码的时候有意识的多想预算一下本身的代码，觉得就会渐渐来啦。
那是我在头条的第一篇，写完实心不太容易，希望开了个好头。码字不容易，臭宝们多多撑持呀，给我点赞呀。
我是帅蛋，我们下次见～
发表评论