算法四大特性
- 輸入輸出
- 有窮性
- 確定性
- 可行性
設計算法四大要求
- 正確性
- 可讀性
- 健壯性
- 時間效率高和存儲量低
算法時間復雜度
推導大O階方法:
1.用常數(shù)1取代運行時間中的所有加法常數(shù)。2. 在修改后的運行次數(shù)函數(shù)中拐叉，只保留最高階項岩遗。3. 如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)凤瘦。
常數(shù)階
int sum = 0, n = 100;
sum = n / 2 * (n + 1); //執(zhí)行一次宿礁，所以時間復雜度為O(1)
printf("%d", sum);
線性階
int i, n;
for (i = 0; i < n; i++) {
//取決于n的值，所以時間復雜度為O(n)
}
對數(shù)階
int count = 1
while (count < n) {
count = count * 2 //count的平方 = n蔬芥，所以時間復雜度為O(logn)
}
平方階
int i, j;
for (i = 0; i < n; i++) { //執(zhí)行n次
for (j = 0; j < n; i++) { //執(zhí)行n次
//時間復雜度為O(n2)
}
}
常見的時間復雜度表
| 執(zhí)行次數(shù)函數(shù) | 階 | 非正式術語 |
|---|---|---|
| 12 | O(1) | 常數(shù)階 |
| 2n + 3 | O(n) | 線性階 |
| 3n2 + 2n + 1 | O(n2) | 平方階 |
| 5㏒2n + 20 | O(㏒n) | 對數(shù)階 |
| 2n + 3n㏒2n + 19 | O(n㏒n) | n㏒n階 |
| 6n3 + 2n2 + 3n + 4 | O(n3) | 立方階 |
| 2n | O(2n) | 指數(shù)階 |
常用時間復雜度所耗費的時間從小到大依次是: 0(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2^n) < O(n!) < O(n^n)
