数据结构与算法基础——第01周-算法与算法解析4(1.7)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 平均时间复杂度

有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同

1
2
3
4
例：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在的位置
for(i=0;i<n;i++)
	if(a[i]==e)return i+1;//找到，则返回是第几个元素
return 0;
  • 最好情况：1次
  • 最坏情况：n
  • 平均时间复杂度为：O(n)

二 时间复杂度说明

  • 最坏时间复杂度：指在最坏情况下，算法的时间复杂度
  • 最好时间复杂度：指在最好情况下，算法的时间复杂度
  • 平均时间复杂度：指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长

三 计算时间复杂度规则——加法规则和乘法规则

对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度

3.1 加法规则

1
T(n)+T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

3.2 乘法规则

1
T(n)+T1(n)xT2(n)=O(f(n))xO(g(n))=O(max(f(n)xg(n)))

四 算法效率的比较

4.1多项式算法时间比较

n f(1) f(logn) f(nlog) f(n2) f(n3) f(2n) f(n!)
1 1 0 0 1 1 2 1
2 1 1 2 4 8 4 2
4 1 2 4 16 64 16 24
8 1 3 8 64 512 256 40320
16 1 4 24 256 4096 65536 2.0923E+13
32 1 5 160 1024 32768 4.295E+09 2.6313E+35

4.2 多项式的递增顺序

常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ... K次方阶 指数阶
O(1) O(log2n) O(n) O(nlog2n) O(n2) O(n3) O(nk) O(n2n)

五 空间复杂度

5.1 概念

空间复杂度

  • 空间复杂度：算法所需存储空间的度量
  • 记作：S(n)=O(f(n))，其中n为问题的规模(或大小)

算法要占据的空间

  • 算法本身要占据的空间，输入/输出，指令、常数、变量等
  • 算法要使用的辅助空间

5.2 示例

示例一

将一维数组a中的n个数逆序存放到原数组中

1
2
3
4
5
【算法1】
for(i=0;i<n/2;i++)
  t=a[i];
  a[i]=a[n-i-1];
  a[n-i-1]=t;

说明：S(n)=O(1)，原地工作

1
2
3
4
5
【算法2】
for(i=0;i<n/2;i++)
	b[i]=a[n-i-1];
for(i=0;i<n;i++)
	a[i]=b[i];

说明：S(n)=O(n);

六 设计好算法的过程