企业官网建设流程全解析

算法效率

1.复杂度的概念
算法在编写成可执行程序后，需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法需要的额外空间。

**2.**时间复杂度
定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
3. . 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。
   那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执⾏次数。通过c语⾔编译链接章节学习，我们知道算法程序被编译后⽣成⼆进制指令，程序运⾏，就是cpu执⾏这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执⾏次数和运⾏时间就是等⽐正相关，这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b。

//count执行次数:eg:voidFunc1(intN){intcount=0;for(inti=0;i<N;i++){for(intj=0;j<N;j++){count++;//执行了N^2次}}}for(intk=0;k<2*N;k++){count++;//执行了N次}intM=10;while(M--){count++;//执行了10次}

分析：
T(N)=N^2+2*N+10

• N=10 T(N)=130
• N=100 T(N)=10210
• N=1000 T(N)=1002010 发现其实占主导影响的就是(N^ 2 ) (这里剧透一下复杂度为O(N^2)
  实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤，因为我们计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

3.1 实际中如何快速计算时间复杂度

计算时间复杂度本质是估算算法属于哪个数量级，那么我们实际中还需要先求出它的执行次数，再求出 T(N) 吗？这样就太麻烦了，所以是不需要的，我们其实可以直接计算。根据前面讲的规则总结一下：f(N) → T(N)

a. 我们只需要关注循环语句，因为普通语句的执行次数都算是常数项，可以忽略。

b. 循环语句中我们只计算内部的一个基本语句执行次数即可，其他语法叠加计算出的也是这个项的系数，系数也是可以忽略的。如：

for(inti=0;i<n;++i){++x;}

我们直接计算++x的执行次数为 N 即可，i < n和++i也一起计算的话影响的也是系数，系数最后还是被忽略掉了。

c. 多个循环语句，一般优先看嵌套层数最多的循环，找出最高阶项。一般一层循环就是 O(N)，两层就是 O(N^2)，三层循环是 O(N^3)，但是实际中需要都算一下，因为有时一层循环不一定是 O(N)，可能是 O(log2N)；两层嵌套循环也可能不是 O(N^2)，而是 O(N) 等等，所以还是要计算具体的算法逻辑。

常见的时间复杂度量级：

O(1) < O(logN) < O(N) < O(N * logN) < O(N^2) < O(N^3) < O(2^N) < O(N!)

3.⼤O的渐进表⽰法

⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号
推导⼤O阶规则

1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，
   低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数
   对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。即O(1)
   所以上方代码的时间复杂度N^ 2+2*N+10,保留高阶项，除去低阶项和常数项，变为O(N^2)

4.1 时间复杂度计算示例

4.1.1

voidFunc2(intN){intcount=0;for(intk=0;k<2*N;k++){count++;}intM=10;while(M--){count++;}printf("%d ",count);}

Func2()执行的次数:
T(N)=2N+10 根据规则，即O(N)

4.1.2

voidFunc3(intN,intM){intcount=0;for(intk=0;k<2*N;k++){count++;}for(intk=0;k<M;k++){count++;}printf("%d ",count);}

Func3中因为不知道M和N的大小，所以写成O(M+N)

4.1.3

voidFunc4(intN,intM){intcount=0;for(intk=0;k<100;k++){count++;}printf("%d ",count);}

Finc4: O(1)

4.1.4

constchar*strchr(constchar*str,intcharacter){constchar*s_begin=str;while(*s_begin!=character){if(*s_begin=='\0')returnNULL;s_begin++;}returns_begin;}

1）若要查找的字符在字符串第⼀个位置，则：T (N) = 1
2）若要查找的字符在字符串最后的⼀个位置，则：T (N) = N
3）若要查找的字符在字符串中间位置，则：T (N) =N/2
4）平均情况:(1+2+3+4+···+n)*1/n=(1+n)/2
因此：strchr的时间复杂度分为：
最好情况： O(1)
最坏情况： O(N)
平均情况： O(N+1/2) 即O(N)

总结：

通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
平均情况：任意输⼊规模的期望运⾏次数
最好情况：任意输⼊规模的最⼩运⾏次数(下界)
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况

4.1.5

voidBubbleSort(int*arr,intn){assert(arr);for(intnum=n;n>0;n--){intchange=0;for(inti=1;i<num;n++){if(arr[i-1]>arr[i]){swap(&arr[i-1],&arr[i]);change=1;}}if(change==0)break;}}

1）若数组有序，则：T (N) = N
2）若数组有序且为降序，则：T (N) =(1+2+3+…+(n-1))=n(n+1)*1/2
时间复杂度一般为最差情况，即T(N)=O(N^2)
4.1.6

voidtest(intn){intnum=1;while(num<n){num*=2;}}

n=2时，执⾏次数为1
当n=4时，执⾏次数为2
当n=16时，执⾏次数为4
假设执⾏次数为 x ，则 2x =N
因此执⾏次数： x = logN
因此：test的时间复杂度取最差情况为：O(logN)

注意课件中和书籍中 log2N 、log N 、lgN表⽰

当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表⽰为 (logN)不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ (logN)

4.1.7
递归函数

intfunc(intn){if(0==n)return1;returnfunc(n-1)+n;}

调用1次，O(1),调用N次,即最坏情况:O(N)

经典题目:

下列函数的时间复杂度是

intfunc(intn){inti=0,sum=0;while(sum<n)sum+=++i;returni;}

本题要计算循环执⾏次数相⽐前⾯的题要绕⼀些，假设循环执⾏x次，本题中每次循环sum +=++i的结果
i=0时，sum+=1;
i=1时，sum+=2;
i=2时，sum+=3；
…
i=x-1时，sum+=x
循环结束时， sum = 1 + 2 + 3 + … + x >= n，则 (x+1)x/2>=n
则整体时间复杂度为 O(n^1/2)

5. 空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使⽤⼤O渐进表⽰法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定
5.1.1

voidBubbleSort(int*arr,intn){assert(arr);for(intnum=n;n>0;n--){intchange=0;for(inti=1;i<num;n++){if(arr[i-1]>arr[i]){swap(&arr[i-1],&arr[i]);change=1;}}if(change==0)break;}}

函数栈帧在编译期间已经确定好了，只需要关注函数在运⾏时额外申请的空间。BubbleSort额外申请的空间有change等有限个局部变量，使⽤了常数个额外空间因此空间复杂度为 O(1)

5.1.2

intfunc(intn){if(0==n)return1;returnfunc(n-1)+n;}

func递归调用了N次，额外开辟了N个函数栈帧，每个栈帧用了常数个空间,空间复杂度为：O(N)

递归算法的空间复杂度通用公式：

对于递归算法，空间复杂度主要取决于递归调用的深度以及每次递归中额外开辟的空间。可以总结为：
递归算法的空间复杂度等于每一层递归额外空间之和，再取大 O 渐进表示。

举例说明：

intfunc(intn){if(0==n)return1;returnfunc(n-1)+n;}

• 递归深度 M = N；
• 每层递归只用了常数个局部变量，即 M = O(1)；
• 因此 S(N) = O(N × 1) =O(N)。

再比如下面这个递归，每层都开辟了一个大小为 N 的数组：

voidfunc(intn){if(n==0)return;intarr[n];// 每层额外开辟 O(N) 空间func(n-1);}

• 递归深度 M = N；
• 每层额外空间 Mᵢ = O(N)；
• 因此 S(N) = O(N × N) =O(N^2)。

小结：计算递归算法的空间复杂度时，先看递归深度 M，再看每层递归额外申请的空间 Mᵢ，两者相乘（求和后取最高阶）即为最终的空间复杂度。注意函数调用时压栈的参数、返回地址等属于常数级开销，通常可以忽略。

越靠左算法越快，越靠右越慢
O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

. 复杂度算法题 (引用)

6.1 旋转数组

给定⼀个整数数组 nums ，将数组中的元素向右轮转 k 个位置，其中 k 是⾮负数。如果我们采⽤每次将数组中数据右轮转⼀位，轮转k次的思路，则时间复杂度为O(N^2) ，空间复杂度为 O(1)
思路一
时间复杂度O(N^2),循环K次将数组所有元素右移一位

voidrotate(int*nums,intnumsSize,intk){intend=nums[numsSize-1];while(k--){for(inti=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=end;}}

思路二

空间复杂度 O(N)申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

给定⼀个整数数组 nums ，将数组中的元素向右轮转 k 个位置，其中 k 是⾮负数.如果我们采⽤新的思路空间换时间，开辟⼀个额外的跟nums⼀样⼤的临时数组tmp，将nums的后k个数据挪动到tmp的前k个位置，再将nums前n-k个挪动到tmp的后n-k个位置，再将tmp数组中的值拷⻉回到nums数组，则时间复杂度为 T (N) = O(N) ，空间复杂度为S(N) = O(N)

voidrotate(int*nums,intnumsSize,intk){k%=numsSize;if(k==0)return;inttmp[k];// 变长数组，C99 起支持；也可写成 int tmp[numsSize]// 拷贝 nums 中的后 k 个到 tmp 的前 k 个位置intj=0;for(inti=numsSize-k;i<numsSize;++i){tmp[j++]=nums[i];}// 从后往前拷贝 nums 前 n-k 个到后 n-k 个位置for(inti=numsSize-k-1;i>=0;--i){nums[i+k]=nums[i];}// 将 tmp 数组中的值拷贝回到 nums 数组for(inti=0;i<k;++i){nums[i]=tmp[i];}}

思路三
空间复杂度 O(1)

• 前n‑k个逆置：4 3 2 1 5 6 7
• 后k个逆置 ： 4 3 2 1 7 6 5
• 整体逆置 ： 5 6 7 1 2 3 4

给定⼀个整数数组 nums ，将数组中的元素向右轮转 k 个位置，其中 k 是⾮负数。 有没有既省空间⼜省时间的思路呢？将nums中所有数据逆置⼀遍，再分别前k个逆置和后n-k个逆置，则时间复杂度为 T (N) = O(N) ，空间复杂度为 S(N) = O(1)

voidreverse(int*nums,intbegin,intend){while(begin<end){inttmp=nums[begin];nums[begin]=nums[end];nums[end]=tmp;begin++;end--;}}voidrotate(int*nums,intnumsSize,intk){k=k%numsSize;//整体逆置reverse(nums,0,numsSize‑k‑1);//后n-k个逆置reverse(nums,numsSize‑k,numsSize‑1);//前k个逆置reverse(nums,0,numsSize‑1);}