算法复杂度(二)

文章目录

• 一、算法的复杂性

• 1.时间复杂度

• (1)时间复杂度介绍
• (2)常数阶 O(1)
• (3)对数阶 O（logn）
• (4)线性阶 O(n)
• (5)二维阶 O(nlogn)
• (6)平方阶 O(n²)
• (7)立方阶 O(n³)

• 2.空间复杂度

• (1)常数阶 O(1)
• (2)常数阶 O(n)

• 3.列出一些常用算法的时间复杂性和空间复杂性
• 4.结束语

一、算法的复杂性

[ 来自360百科 ]将算法编制成可执行程序后，运行所需的资源包括时间资源和内存资源。应用于数学和计算机导论。不同的算法可以解决同一个问题，算法的质量会影响算法甚至程序的效率。算法分析的目的是选择合适的算法和改进算法。对算法的评价主要考虑时间复杂性和空间复杂性。以下是时间复杂性和空间复杂性的解释。

1.时间复杂度(1)时间复杂度介绍

什么是时间复杂性？算法的执行时间是指算法所有句子执行的时间总和，我们可以计算每个句子的执行时间，但由于句子的执行速度和计算机的软硬件（硬盘、存储控制器、界面卡、CPU）环境影响很大。一个句子可能在不同的设备上有不同的执行时间。显然，计算句子的执行时间是非常不明智的。此时，一个新的解决方案诞生了。既然我们想准确地得到句子的执行时间，那就有点麻烦了，为什么不从不同的角度思考问题，引入我们今天的主角，复杂性，我们只需要规定句子的复杂性，只需要知道执行句子的一般时间（可以认为复杂性与时间成正比，时间越多，复杂性越高），规定句子执行时间与句子执行次数成正比，这就是时间的复杂性。在算法分析中，句子的总执行次数T(n)它是关于问题规模n的函数，然后分析T(n)随n的变化，确定T的变化(n)的数量级。

 

记录算法的时间复杂性，即算法的时间量：T(n)= O(f(n))。

用大写O()来反映算法时间的复杂性，我们称之为 大O记法。

一般情况下，随着输入规模n的增加，T(n)增长最慢的算法是最优算法。

 

常见的算法时间复杂度包括： O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!)

复杂度对应的名称有:常数阶、对数阶、线性阶、二维阶、平方阶、立方阶、指数阶、乘阶

那么，我们应该如何计算现有算法的时间复杂性呢？只要记住以下三句话！

1.用常数1代替运行时间中的所有加法常数。2.只要高阶项，就放弃低阶项。3.不要使用高阶项系数。

下面，用一些例子来介绍常见的时间复杂性。

(2)常数阶 O(1)

例1：

int a = 2;int b = 3;int temp;  temp = a;     //执行第一次a = b;        //执行第一次b = temp;     ///执行第一次//三个语句共执行(1+1+1)= 三次，根据第一句，用常数1代替运行时间中的所有加法常数。//所以3用1代替，所以程序完成后，时间复杂度为O(1)。

例2：

printf("hello world");  //执行第一次printf(“坚持就会有收获”;////执行第一次intint sum=0;    int n=10; sum=(n*(n+1))/2;//执行第一次printf(“加油！");///执行第一次//三个语句共执行(1+1+1+1)= 根据第一条的规定，用常数1代替运行时间中的所有加法常数4次。//所以4用1代替，所以程序完成后，时间复杂度为O(1)。

看到这里，一些可爱的新人可能会问为什么它类似于int sum=0的语句为什么不算执行次数？因为int sum=0这是定义变量。不是句子，请看文章开头的黄色句子，那么那些算作句子呢？ 以C语言为例：

语句

解释

赋值语句

变量=表达式

输入语句

scanf

输出语句

printf

条件语句

If

循环语句

While for

然后往下看，先复习一下什么是对数，有些人可能已经忘记了。 a^x = N ( a > 0 && a != 1 ) 也就是说，x以a为底，n对数，a称为对数底，N称为真数。

(3)对数阶 O（logn）

int sum= 1;int n = 1000;while (sum < n){ sum = sum * 2;}///第一次执行:sum=1*2=2  2^1//第二次执行:sum=2*2=4  2^2//第三次执行:sum=4*2=8  2^3//第四次执行：sum=8*2=16 2^4//第X次执行：^x=n，x=log2n，所以复杂度是O（logn）。

(4)线性阶 O(n)

for (int i = 0; i < n; i++)  //执行n+1次 {  printf(“坚持就会有结果！”;   ///执行n次 } //n+n+三句话可以得到1=2n+1//，复杂度为O(n)。

(5)二维阶 O(nlogn)

for (int i = 0; i < n; i++)  //执行n+1次{while (sum < n){sum = sum * 2;}}//二维阶又称线性对数阶，将对数阶 O（logn）N次代码循环是

(6)平方阶 O(n²)

for (int i = 0; i < n; i++){ for (int j = 0; j <= n; j++) {  j = 1;  j++; }}///平方阶就是复杂度。 O(n)嵌套代码一次

(7)立方阶 O(n³)

///立方阶是复杂的 O(n)代码嵌套两次，这里就不赘述了。

2.空间复杂度

一个算法的空间复杂性类似于时间复杂性的讨论(SpaceComplexity)S(n)定义为该算法消耗的存储空间，也是问题规模n的函数。渐近空间的复杂性通常被称为空间复杂性。

空间复杂性是算法在执行过程中临时占用存储空间大小的测量，记录为S(n)=O( f(n) )。常见的空间复杂性包括 O(1)，O(n)，O(n^2)。

(1)常数阶 O(1)

int i = 1;  int j = 2; ++i; j++; int m = i + j; ///代码中的i j m变量分配的空间不会随着处理数据量的变化而变化，因此其空间复杂性S(n)=O(1).

(2)常数阶 O(n)

int n = 20;int *a = new int[n];int j;for (int i = 1; i <= n; i++){ j = i; j++;}///在这个代码中，第一行new有一个数组，大小为n。虽然有循环，但没有分配空间。//因此，空间的复杂性主要在第一行，即S(n)=O(n).

3.列出一些常用算法的时间复杂性和空间复杂性

4.结束语

算法的复杂性是我们进入数据结构和算法的第一步，在这里，我想对你说，永远不要认为数据结构或算法，无用，无用，是大用途，永远不要认为他们可以根据需要写得很好