算法复杂度

文章目录

• 一、算法复杂度的概念
• 二、时间复杂度
• • 1.大O的渐进表示法
• 三、空间复杂度

提示：以下是本篇文章正文内容，下面案例可供参考

一、算法复杂度的概念

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

• 时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。

二、时间复杂度

在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。

• 1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译
     器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
• 2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
• 3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

1.大O的渐进表示法

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

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

void Fun(int n) 
{ 
 int count = 0; 
 for (int k = 0; k < 2 * n ; ++ k) 
 { 
 ++count; 
 } 
 int m = 10; 
 while (m--) 
 { 
 ++count; 
 } 
 printf("%d\n", count); 
} 

执⾏的基本操作次数:
T (N) = 2N + 10 ,根据推导规则第3条得出,Fun的时间复杂度为:O(N)

• ⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

• 最坏情况：任意输⼊规模的最⼤运⾏次数(上界)

• 平均情况：任意输⼊规模的期望运⾏次数

• 最好情况：任意输⼊规模的最⼩运⾏次数(下界)

三、空间复杂度

• 间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。
• 空间复杂度不是程序占⽤了多少的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。
• 空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。

注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

long long Fun(size_t N) 
{ 
 if(N == 0) 
 return 1; 
 else
 return Fun(N-1)*N; 
}

Fun递归调⽤了N次，额外开辟了N个函数栈帧，每个栈帧使⽤了常数个空间因此空间复杂度为：O(N)