算法的时空复杂度

2020-04-29 22:32:24 Albin Wong 2790

### 一、 算法  
运算的实现是指该运算的算法。算法是计算机科学的一个基本概念，也是程序设计的一个核心概念。

#### 1. 算法的描述：
- 程序
- 介于自然语言和程序设计语言的伪代码
- 非形式算法(自然语言) 
- 框图(N-S图)

#### 2. 算法的好坏评价因素
- 正确性:能正确地实现预定的功能，满足具体问题的 需要。
- 易读性:易于阅读、理解和交流，便于调试、修改和 扩充。
- 健壮性:即使输入非法数据，算法也能适当地做出 反应或进行处理，不会产生预料不到的运行结果。
- 时空性:一个算法的时空性是指该算法的时间性能 (或时间效率)和空间性能(或空间效率)，前者是算法包含的计算量，后者是算法需要的存储量。

#### 3. 算法的效率度量：时间复杂度和空间复杂度
解决同一问题的算法可以有多种。 希望从中选出最优的算法，效率高或者存储空间小。需要对算法进行评估、分析。通常考虑以下两个度量：
- **时间复杂度**：算法运行时需要的总步数。
- **空间复杂度**：算法执行时所占用的存储空间。

#### 4. 如果确定算法的计算量  
- 合理地选择一种或几种操作作为“标准操作”，无特殊说明，*默认以赋值语句作为标准操作*。
- 确定每个算法共*执行多少次标准操作*，并将此*次数*规定为该算法的*计算量*。

#### 二 、 时间复杂度 
一个算法执行所耗费的时间。一个算法中的语句执行次数称为语句频度或时间频度记为T(n);时间复杂度主要分析T(n)的数量级，通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。

##### 1. 最好情况、最坏情况和平均情况
- 以算法在**所有输入下的计算量的最大值**作为算法的计算量，称为*算法的最坏情况时间复杂度*
- 以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为*算法的平均情况时间复杂度*。
- 最坏情况时间复杂度和平均情况时间复杂度通称为*时间复杂度*

假定采用链式存储结构，在一个一维数组中[1,2,3,4,5,..,n]
如果该数组中数据是无序分布时，我们查找是3，最好的情况是3在第一顺位，则需要查找1次;最坏的情况时.3出现最后一个，则需要查找n次。

##### 2. 大O表示
n称为问题的规模，当n不断增加时，时间频度T(n)函数中增长最快的部分这个数量级函数一般用大 O表示也称渐进表示法，记做 O(f(n))。它 不考虑具体的运行时间，只给出算法在问题规模 n 下执行时间的上界。T(n) =O(f(n))称为 算法的渐进时间复杂度，简称时间复杂度。

```c
// 矩阵运算—矩阵乘法
Void matrixmlt ( ......)
{
	for(i=0; i<n; i++)
	{
		for (j = 0; j < n; j++)
		{
			C[i][j] = 0;
			for (k = 0; k < n; k++)
				C[i][j] += A[i][k] * B[k][j];
		}
	}
}
```
此算法的最坏时间复杂度和平均时间复杂度均为n的函数:
T(n) = n2 + n3
T(n) 与 n3的数量级相同, 称此算法的时间复杂度量级为O(n3)，记作T(n)= O(n3), 将O(n3)称作时间复杂度。
另外，时间频度不同，但时间复杂度可能相同。如：T(n)=n2+5与T(n)=3n2+3n+1,当 n 增大时，后面两项可以忽略掉, 它们的频度不同，但时间复杂度相同，都为O(n2)

##### e.g.
设变量a、b、c、d中各含一个整数。求a、b、c中的最大值与d的乘积
```c
void max1(int a,b,c,d)
{
	a*=d;b*=d;c*=d;
	if(a>b) x=a;
	else x=b;
	if(c>x) x=c;
	printf(“%d\n”,x);
}

void max2(int a,b,c,d)
{
	if(a>b) x=a;
	else x=b;
	if(c>x) x=c;
	x*=d;
	printf(“%d\n”,x);
}
// 算法max1和max2的最坏情况时间复杂度分别为5和3
```

*时间复杂度 e,g.*
```c
// 编制函数求1! + 2! + 3! + ... + n!. 
int fact1(int n)
{
	int i,j,temp,s;
	s = 0;
	for (i = 0; i <= n; i++)
	{
		temp = 1;
		for (j = 0; j <= i; j++) 
		{
			temp = temp * j;
		}
		s = s + temp;
	}
	return s;
}
```
##### 常见的时间复杂度比较
常数阶O(1) < 对数阶O(log2n) < 线性阶O(n) < 线性对数阶 O(nlog2n) < 平方阶O(n2) < 多项式阶O(nC) < 指数阶O(Cn)

将时间复杂度记为输入数据规模n的函数，若求解问题需要执行n2次操作，则记作O(n2)
1. 常数阶 O(1)
```c
	int n = 100; // 1 次
	int sum = (1 + n) * n / 2; // 1次
	printf("%d\n", sum); // 1次
```
上面语句共三条操作，单条操作的频度为1， f(n) = 3；即使有成千上万条操作，也只是个较大常数，不管这个常数是多少，与数据的规模大小 n 无关，这一类的时间复杂度为O(1)；
2. 对数阶 O(log2n)
```c
int cnt = 1;
while (cnt < n)
 cnt *= 2 // O(1)
```
 cnt 乘以多少个 2 以后才能大于等于 n? 假设个数是 x，也就是求 2x = n ，即 x = log2n，所以这个循环的时间复杂度就是 O(log2n)
 
3. 多项式阶O(nC)
```c
	int a,b,c,d,n,i,j,x,y,z,u,v,k;
	 a = 1;
	 b = 2;
	 c = 3;
	 n = 100;

for( i = 0; i <= n; i++)
	{
 	for ( j = i; j <= n; j++)
		{
 	 x = i * i;
 	 y = j * j;
 	 z = i * j;
		}
	}
	for ( k = 0; k <= n; k++)
	{
 	u = a * k + b;
 	v = c * c;
	}
	d = 4;
```
代码分成 4 部分：
第 1 部分是 声明所有变量及a、b、c、n 赋值语句，执行次数也就是 5 次；
第 2 部分是3n2 ，因为是循环结构，里面有 x、y、z 这 3 个赋值语句，每个语句执行了n2次；
第 3 部分是 2n，因为里面是 2 个赋值语句，每条语句被执行了 n 次；
第 4 部分是常数 1，只有 d 这么 1 条赋值语句。
所以我们得到的T(n) = 3 + 3n2 + 2n + 1 = 3n2 +2n + 4 ，看到最高指数项是n2做主导，这个代码片段的数量级就是O(n2) 。

##### 各种时间复杂度与时间的关系

| n | f(n) = log2n | f(n) = n | f(n) = n2 | f(n) = n3 | f(n) = n4 | f(n) = n10 | f(n) = 2n |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 10 | 0.0015 μs | 0.005 μs | 0.05 μs | 0.5 μs | 5 μs | 5s | 0.5 μs |
| 30 | 0.0025 μs | 0.015 μs | 0.45 μs | 13.5 μs | 405 μs | 3.42 d | 0.5 s |
| 50 | 0.003 μs | 0.025 μs | 1.25 μs | 62.5 μs | 3.13 ms | 1.55 y | 6.5 d |
| 103 | 0.005 μs | 0.5 μs | 0.5ms | 0.5s | 8.33 min | 1.59E13 y | 16E283 y |
| 105 | 0.0085 μs | 50 μs | 5 s | 5.79 d | 1585 y | 1.59E33 y | - |

#### 三、空间复杂度
1. —个算法的空间复杂度定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。通常可记为:S(n) =0(g(n))
其中，g(n)为问题规模 n 的某个函数。
2. 空间复杂度是对一个程序在运行过程中临时占用存储空间大小的量度。  
一个算法在执行期间所需要的存储空间量包括以下部分:
- 程序代码所占用的空间;  
- 输入数据所占用的空间;  
- 辅助变量所占用的空间，估算算法空间复杂度时，一般只分析辅助变量所占用的空间

e.g.
```c
// 读入 n =100个整数到一个数组中，写出实现该数组进行逆置的算法，并分析算法的空间复杂度
void f1 (int a[], int n)
{
	int i,temp;
	for (i = 0; i < n/2 - 1; i++)
	{
		temp = a[i];
		a[i] = a[n - 1 - i];
		a[n - 1 - i] = temp;
	}
}

void f2 ( int a[], int n)
{
	int i, b[100];
	for (i = 0; i <= n - 1; i++)
		b[i] = a[n - 1 - i];
	for (i = 0; i <= n -1; i++)
		a[i] = b[i];
}
```
*f1与f2解读* 
f1与f2中的时间复杂度都是O(n) 
f1的空间复杂度O(1): 因为该程序只借助了temp一个辅助空间实现 
f2的空间复杂度O(n): 该算法实现声明了b一个长度为100个元素的辅助空间，T(n) = 2n

----
【相关推荐】
- [圈复杂度（Cyclomatic Complexity）](https://www.albinwong.com/W0laY2LX7wXrkz3p.html "圈复杂度（Cyclomatic Complexity）")
- [十大经典排序算法](https://www.albinwong.com/OGB6dQjyZyDkX5NR.html "十大经典排序算法")

(3) Comments

John Doe- Reply

February 26, 2013 at 1:18 pm
- saqib sarwar- Reply
  
  February 26, 2013 at 1:20 pm
  
  Nam liber tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum. Typi non habent claritatem insitam; est usus legentis in iis qui facit eorum claritatem. Investigationes demonstraverunt lectores legere me lius quod ii legunt saepius. Claritas est etiam processus dynamicus, qui sequitur mutationem consuetudium lectorum. Mirum est notare quam littera gothica, quam nunc putamus parum claram, anteposuerit litterarum formas humanitatis per seacula quarta decima et quinta decima. Eodem modo typi, qui nunc nobis videntur parum clari, fiant sollemnes in futurum.
John Doe- Reply

February 26, 2013 at 1:27 pm

Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat.

Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi. Nam liber tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum.

Your email address will not be published. Required fields are marked *

Name *

Email *

Website

Comment

You can use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <cite> <code> <del datetime=""> <q cite=""> <strike> 

算法的时空复杂度

(3) Comments

John Doe- Reply

saqib sarwar- Reply

John Doe- Reply

Leave a Reply