>[success] # 复杂度分析 ~~~ 1.首先要掌握一个数据结构与算法中最重要的概念——复杂度分析 ~~~ >[info] ## 大 O 复杂度表示法 ~~~ 1.概念：算法的「执行时间」与每行代码的「执行次数」成正比'T(n) = O(f(n))', 其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。 1.1.'T(n)' -- 算法执行总时间 1.2.'f(n)' -- 表示每行代码执行的次数总和 1.3.'n' -- 数据的规模的大小 2.大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说， 它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界,举个例子： 'T(n) = 4n^2 - 2n + 2,当 n 增大时，n^2; 项将开始占主导地位，而其他各项可以被忽略' 上面的内容就可以表示为'T(n)=O(4n^2)' 理解：就是O 可以理解我们默认一个常量无穷大的时候，只关心他的主导条件，忽略其他与它 相比可以忽略的条件 -- 也就是无穷大渐近 ~~~ >[danger] ##### 通过代码案例理解(一) ~~~ 1.下面代码是前端的代码，代码实现的是累加求和。 ~~~ ~~~ function cal(n) { let sum = 0 // 运行时间 1 个unit_time let i = 1 // 运行时间 1 个unit_time for(;i<=n;i++){ // 运行时间 n 个unit_time sum = sum + i // 运行时间 n 个unit_time } return sum } console.log(cal(10)) // 55 ~~~ * 分析这段代码的复杂程度 ~~~ 1.参数'n'对应 -- 上面概念讲解里的 '数据的规模的大小' 2.把每行运行时间默认为 1 个unit_time 3.像上面的代码'i' 和 'sum' 都是变量，只会执行一次因此它俩的时间效率分别都是1 个unit_time ，for循环的时间效率是根据'n'的长度来决定的因此是 n 个unit_time 4.所以上面的代码总时长是 '2*unit_time+n*unit_time+n*unit_time'整理可得： (2n+2)*unit_time 5.用大 O 复杂度表示法，取'无穷大渐近'T(n) = O(n) ~~~ >[danger] ##### 通过代码案例理解(二) ~~~ 1.分析下面案例，主要分析的是内层循环代码，因为我们都知道外层循环一次等于内层循环 一遍，因此下面代码中的外层次数是'n',外层每循环一次内层就给来一遍因此内层循环次数就是 'n*n' 2.整理一下，下面代码的执行时间 '3*unit_time + 2n*unit_time +2n^2unit_time'合并可得： 'T(n) = (2n2+2n+3)*unit_time' 3.用大 O 复杂度表示法，取'无穷大渐近'T(n) = O(n^2) ~~~ ~~~ int cal(int n) { int sum = 0; // 1 个unit_time int i = 1; // 1 个unit_time int j = 1; // 1 个unit_time for (; i <= n; ++i) { // n 个unit_time j = 1; // n 个unit_time for (; j <= n; ++j) { // n^2 个unit_time sum = sum + i * j; // n^2 个unit_time } } } ~~~ >[danger] ##### 简单总结 ~~~ 1.所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比 2.大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示 代码执行时间随数据规模增长的变化趋势，所以，也叫作'渐进时间复杂度' 简称'时间复杂度' 3.当 n 很大时公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。 我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的 时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n^2),这是大O符号的在数学中的含义 无穷大 ~~~