时间复杂度与空间复杂度如何计算_求下列算法的时间复杂度和空间复杂度。(60分)void test (int n, int m) {i

如何衡量一个算法的复杂度？

· 时间复杂度
· 空间复杂度
统称为算法复杂度！

时间复杂度

为什么和衡量时间复杂度用执行次数而不是执行时间？？？

答：不同的环境执行的时间是不同的，所以用时间衡量没有意义
只有运行次数永远都是确定的
下列程序会执行多少次？

void Test(int n) 
{ 
 int iConut = 0; 
 for(int i = 0; i < n; ++i) 
   { 
   for(int j = 0; j < n; ++j) 
   { 
   iCount++; 
   } 
 } 
 for(int k = 0; k < 2*n; ++k)
 { 
 iCount++; 
 } 
 int count = 10; 
 while(count--) 
 { 
 iCount++; 
 } 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

f(n)=nn+2n+10
时间复杂度实际就是一个函数，来计算基本操作次数
算法存在最好，最坏和平均情况。在实际中通常关注的是算法的最坏运行情况。

因此用O(f(n))–大0渐进法表示时间复杂度

1：用常数1取代所有的常数

2： 只保留最高阶项

3：如果最高阶不是项数不是1，取出这个常数

void Test1(int n) 
{ 
 int iCount = 0; 
 for (int iIdx = 0; iIdx < 10; ++iIdx) 
 { 
 iCount++; 
 } 
 for (int iIdx = 0; iIdx < 2*n; ++iIdx) 
 { 
 iCount++; 
 } 
}
1
2
3
4
5
6
7
8
9
10
11
12

总执行次数：f(n) = 2*n+10
O（f（n））=n

递归算法：递归总次数*每次递归复杂度，
递归多了容易栈溢出。（栈空间默认大小： windows 1MB，Linux 8MB）

空间复杂度

函数创建对象的个数关于问题规模的表达式，用O的渐进法表示

int Sum(int N) 
{ 
 int count = 0; 
 for(int i = 1; i <= N; ++i) 
 count += i; 
 return count; 
}
1
2
3
4
5
6
7

空间复杂度：O(1)
（创建变量的个数）

long long Fib(int n) 
{ 
 if(n < 3) 
 return 1; 
 return Fib(n-1)+Fib(n-2); 
} 
1
2
3
4
5
6

时间复杂度：O(2^n)
空间复杂度：O(n)

时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差
常用的算法的时间复杂度和空间复杂度：