浅谈算法复杂度

时间复杂度

1. 时间频度

一个算法执行的时间

2.时间复杂度

n 称为事件规模， 当n不断发生变化时， 时间频度T(n)也会不断变化, 这种变化规律称之为时间复杂度一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度

复杂度分析

通常一个算法的复杂度是由其输入量决定的，随着输入的增加，复杂度随之变化.为了降低算法复杂度，应当同时考虑到输入量，设计较好的算法

实际计算算法复杂度(以时间为标准)

删除影响不大的常数相

O(1)

int aFunc(void) {
printf("Hello, World!\n"); // 需要执行 1 次
return 0; // 需要执行 1 次
}
//T(n) = 2 则复杂度为O(1)

O(n)

int aFunc(int n) {
for(int i = 0; i
O(n^2)
void aFunc(int n) {
// 第一部分时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
// 第二部分时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
//T(n) = n + n*(n + 1) + n*n + n+(n+1) ，则O(n^2)
含有判断的算法
void aFunc(int n) {
if (n >= 0) {
// 第一条路径时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("输入数据大于等于零\n");
}
}
} else {
// 第二条路径时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("输入数据小于零\n");
}
}
}
//O(n^2) 和 O(n), 选取最大的O(n^2)
O(log(n))
void aFunc(int n) {
for (int i = 2; i < n; i++) {
i *= 2; //执行次数 t^2 = n; 执行次数t =log(2)(n)
printf("%i\n", i);
}
}
T(t) = log(2)(n) = log(2n) 则O(log(n))
O(2^n)
long aFunc(int n) {
if (n <= 1) {
return 1;
} else {
return aFunc(n - 1) + aFunc(n - 2);
}
}
//T(n) = T(n - 1) + T(n - 2)， 通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。

關鍵字: World 算法复杂度 时间复杂度