 到 O(N)：程序员进阶路上必修的算法效率课！)
个人主页:Marathon_X 个人专栏:专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践《排序详解》算法思路、解题技巧与高效编程实践目录一、为什么要学习算法二、算法的效率报告2.1 为什么直接计时不科学2.2 什么是时间复杂度案例分析计算执行次数T ( N ) T(N)T(N)2.3 算法效率的身份证大O OO表示法推导大O OO阶的 3 个规则2.4 常见的时间复杂度示例最好、最坏和平均情况2.5 简单提一下空间复杂度2.6 总结与下一步前言作为一名“程序猿”大家应该都听过这么一句话程序数据结构算法。这句话是由瑞士计算机科学家尼古拉斯·沃斯Niklaus Wirth在 1984 年获得图灵奖时说的一句话这位大佬还以这句话为名出了一本书《Algorithms Data StructuresPrograms》从此这句话就成为了大家耳熟能详的一句名言。随着时间的推移不管这句话是不是非常准确但至少能说明数据结构与算法对程序来说是非常核心的基础如果我们想要写出更多优秀优雅的代码那么数据结构与算法是必须要掌握好的。一、为什么要学习算法很多人可能觉得我不会算法代码一样写得很溜算法这东西似乎用处不大。现在互联网的发达我们想要什么几乎都可以在网上找到现成的各种框架功能十分强大似乎看起来确实不用算法也可以写出“好代码”。然而假如我们不懂算法比如项目中用到了排序我们如何评估代码的执行效率再比如最常用的ArrayList和LinkedList我们该如何选择又比如说我们需要去集合中找某一个数又该如何写出性能优秀的代码呢同样的代码如何判断谁的代码是优秀的代码可读性可扩展性健壮性可能都可以用来判定然而这些东西我觉得并不能直接体现出你代码的优秀因为对用户而言访问你的代码响应速度快那就是优秀的代码相反动辄响应几秒甚至更长时间的接口恐怕就算你可读性再好再健壮也称不上是好代码。所以说一段代码是否优秀最直接的判断标准就是性能而如果要写出高性能的代码那么就必须要了解算法而且抛开这个因素但凡不想一辈子都写 CRUD 代码的也需要去了解算法我们使用的很多框架和中间件底层都有数据结构和算法的身影学好算法对我们源码阅读时理解其设计思想也是大有裨益的。要说功利性的目的那就是面试目前很多大厂的面试算法基本必面所以想进大厂的话咱们也得好好学学算法。二、算法的效率报告当你开始学习算法时你一定想知道我写的代码到底快不快想象一下你写了两种不同的代码来解决同一个问题。你想知道哪一个效率更高于是你运行了一下发现第一个程序运行了 5 秒第二个只运行了 0.5 秒。所以第二个程序更快别急着下结论这个简单的计时方法就像是给算法做了一个不靠谱的体检。2.1 为什么直接计时不科学在计算机科学中我们衡量一个算法的好坏通常从两个维度来衡量时间和空间。但我们为什么不直接用秒表来计时呢原因很简单程序的实际运行时间会受到很多外部因素的影响硬件配置你在老旧电脑上跑 10 秒的代码换到一台高性能服务器上可能瞬间完成。同一个算法程序用一个低配置机器和新高配置机器运行时间也不同。编程语言和编译器不同的编译器编译出来的指令条数可能不一样。同一个算法程序用一个老编译器进行编译和新编译器编译在同样机器下运行时间不同。数据规模运行时间会随着输入数据的增大而变化。程序写好后才能测试时间只能程序写好后测试不能写程序前通过理论思想计算评估。直接计时无法脱离具体的编译和运行环境也无法在写程序前进行理论评估。为了更科学、更公平地评估算法效率我们引入了一个概念时间复杂度。2.2 什么是时间复杂度时间复杂度是一个函数式T ( N ) T(N)T(N)它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率。这个T ( N ) T(N)T(N)并不是指秒而是指程序中基本操作执行的次数。简单来说我们不再数“秒”而是数步。算法程序被编译后生成二进制指令程序运行就是CPU执行这些编译好的指令。我们通过程序代码或者理论思想计算出程序的执行次数的函数式T ( N ) T(N)T(N)。假设每句指令执行时间基本一样那么执行次数和运行时间就是等比正相关这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。案例分析计算执行次数T ( N ) T(N)T(N)来看一段代码片段假设它是一个函数F u n c 1 ( N ) Func1(N)Func1(N)voidFunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;while(M--){count;}}这段代码中所有基本操作的精确执行次数函数T ( N ) T(N)T(N)可以粗略地写为T ( N ) N 2 2 N 10 T(N) N^2 2N 10T(N)N22N10当我们取不同的N NN值时可以看到N 2 N^2N2对结果的影响最大N 10 N10N10T ( N ) 130 T(N)130T(N)130N 100 N100N100T ( N ) 10210 T(N)10210T(N)10210N 1000 N1000N1000T ( N ) 1002010 T(N)1002010T(N)1002010通过对N NN取值分析对结果影响最大的一项是N 2 N^2N2。当N NN变得非常大时常数项和低阶项对结果的影响很小。2.3 算法效率的身份证大O OO表示法在实际计算时间复杂度时我们不追求精确的执行次数。我们更关心的是当N NN不断变大时执行次数的增长趋势增长量级。复杂度的表示通常使用大O OO渐进表示法。因此我们使用**大O OO渐进表示法Big O notation**来描述这种渐进行为。推导大O OO阶的 3 个规则要从T ( N ) T(N)T(N)推导出O ( N ) O(N)O(N)只需遵循以下三个步骤只保留最高阶项去掉那些低阶项因为当N NN不断变大时低阶项对结果影响越来越小当N NN趋于无穷大时就可以忽略不计了。去除最高阶项的常数系数如果最高阶项存在且不是 1则去除这个项目的常数系数因为当N NN不断变大这个系数对结果影响越来越小当N NN趋于无穷大时就可以忽略不计了。常数项用 1 取代T ( N ) T(N)T(N)中如果没有N NN相关的项目只有常数项用常数 1 取代所有加法常数。应用示例对于T ( N ) N 2 2 N 10 T(N) N^2 2N 10T(N)N22N10保留最高阶项N 2 N^2N2去除系数系数为 1不变N 2 N^2N2最终时间复杂度为O ( N 2 ) O(N^2)O(N2)对于T ( N ) 2 N 10 T(N) 2N 10T(N)2N10保留最高阶项2 N 2N2N去除系数 2N NN最终时间复杂度为O ( N ) O(N)O(N)2.4 常见的时间复杂度示例大O OO复杂度名称描述/增长趋势代码示例O ( 1 ) O(1)O(1)常数阶无论数据规模N NN多大执行次数都是固定的常数。最快顺序执行的语句。例如F u n c 4 Func4Func4中循环 100 次其T ( N ) 100 T(N)100T(N)100因此时间复杂度为O ( 1 ) O(1)O(1)。O ( log N ) O(\log N)O(logN)对数阶执行次数随着N NN的增大增长非常缓慢。函数func5中cnt每次乘以 2直到大于N NN执行次数x xx满足2 x N 2^xN2xN因此x log 2 N x \log_2 Nxlog2N时间复杂度为O ( log 2 n ) O(\log_2 n)O(log2n)通常简写为O ( log n ) O(\log n)O(logn)。O ( N ) O(N)O(N)线性阶执行次数与N NN成正比。单层循环遍历数组、链表。例如阶乘递归F a c ( N ) Fac(N)Fac(N)会调用N NN次时间复杂度为O ( N ) O(N)O(N)。O ( N log N ) O(N \log N)O(NlogN)线性对数阶相当于N NN次对数操作。优秀的排序算法如归并排序的平均情况。O ( N 2 ) O(N^2)O(N2)平方阶执行次数是N NN的平方。双重循环。例如冒泡排序的最坏情况执行次数为N ( N 1 ) 2 \frac{N(N1)}{2}2N(N1)时间复杂度取最差情况为O ( N 2 ) O(N^2)O(N2)。O ( 2 N ) O(2^N)O(2N)指数阶效率极低程序性能会急剧恶化。最好、最坏和平均情况有些算法比如查找和排序的执行次数会根据输入数据的不同而变化。最好情况O ( 1 ) O(1)O(1)任意输入规模的最小运行次数下界。例如strchr查找字符若要查找的字符在字符串第一个位置则T ( N ) 1 T(N)1T(N)1时间复杂度为O ( 1 ) O(1)O(1)。最坏情况O ( N ) O(N)O(N)任意输入规模的最大运行次数上界。例如strchr查找字符若要查找的字符在字符串最后一个位置则T ( N ) N T(N)NT(N)N时间复杂度为O ( N ) O(N)O(N)。平均情况任意输入规模的期望运行次数。大O OO渐进表示法在实际中一般情况关注的是算法的上界也就是最坏运行情况。2.5 简单提一下空间复杂度空间复杂度也是一个数学表达式是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。空间复杂度算的是变量的个数而不是程序占用了多少bytes的空间。它也使用大O OO渐进表示法。你需要关注的是函数在运行时候显式申请的额外空间。函数运行时所需要的栈空间存储参数、局部变量等在编译期间已经确定好了。O ( 1 ) O(1)O(1)(常数空间)算法只使用了有限个额外的局部变量。例如冒泡排序B u b b l e S o r t BubbleSortBubbleSort额外申请了exchange等有限个局部变量使用了常数个额外空间因此空间复杂度为O ( 1 ) O(1)O(1)。O ( N ) O(N)O(N)(线性空间)算法所需的额外空间与输入规模N NN成正比。例如阶乘递归F a c FacFac调用了N NN次额外开辟了N NN个函数栈帧每个栈帧使用了常数个空间因此空间复杂度为O ( N ) O(N)O(N)。总结在计算机发展的早期计算机的存储容量很小所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展存储容量已经很高所以我们如今已经不需要再特别关注一个算法的空间复杂度。2.6 总结与下一步时间复杂度就是算法的“执行步数”它帮我们脱离硬件和环境用一种数学化的方式来衡量算法的效率。掌握大O OO表示法及其推导规则是学习数据结构和算法的第一步也是校招笔试面试的必考内容。
)
