算法的時間復雜度推導方法
語句頻度
語句頻度是指語句的重復執(zhí)行次數(shù)。
推導大O階方法
方法
- 用常數(shù)1取代運行時間中的所有加法常數(shù)。
- 在修改后的運行次數(shù)函數(shù)中唠帝，只保留最高階項澳泵。
- 如果最高階項存在且不是1，則去除與這個項相乘的乘數(shù)瓢谢。
常數(shù)階舉例運用
右側注釋中的 num 表示語句執(zhí)行的次數(shù)畸写。
int sum = 0, n = 100; /* num = 1 */
sum = (n+1) * n / 2; /* num = 1 */
printf("%d", sum); /* num = 1 */
這段代碼的運行次數(shù)函數(shù)是 f(n) = 1 + 1 + 1 ，根據(jù)“推導大O階方法”中的第一條規(guī)則氓扛，把
1 + 1 + 1 用 1 替換枯芬，運行次數(shù)函數(shù)變成了 f(n) = 1。該函數(shù)只有常數(shù)項，只需使用規(guī)
則1就可以推導出它即這段代碼的時間復雜度是 O(1) 千所。
假如 sum = (n+1) * n / 2 執(zhí)行3次狂魔，將上面的代碼修改為:
int sum = 0, n = 100; /* num = 1 */
sum = (n+1) * n / 2; /* num = 1 */
sum = (n+1) * n / 2; /* num = 1 */
sum = (n+1) * n / 2; /* num = 1 */
printf("%d", sum); /* num = 1 */
這段代碼的運行次數(shù)函數(shù)是 f(n) = 1 + 1 + 1 + 1 + 1 。 按照推導大O階第一條規(guī)則淫痰，用1取代
所有的加法常數(shù)最楷，這段代碼的運行次數(shù)函數(shù)是 f(n) = 1。這段代碼的時間復雜度依然是 f(n) = O(1) 黑界。
所有這類代碼的時間復雜度都是 O(1)管嬉。O(1)叫做常數(shù)階。不存在 O(2) 朗鸠、 O(9) 這類寫法蚯撩。
線性階舉例運用
code-3
int i;
for(i = 0; i < n; i++){
// 時間復雜度為O(1)的代碼
}
code-3的運行次數(shù)函數(shù)是 f(n) = n * 1。加法常數(shù)為0個烛占，跳過規(guī)則一胎挎。變量n的最高階是 n * 1，無
其他項忆家，跳過規(guī)則二犹菇。n * 1中的系數(shù)本來就是1，也可以直接跳過規(guī)則三芽卿，得到code-3的時間復雜度是
f(n) = O(n)揭芍。
code-4
int i;
for(i = 0; i < n; i++){
// 時間復雜度為O(1)的代碼
}
int j;
for(j = 0; j < m; j++){
// 時間復雜度為O(1)的代碼
}
code-4的運行次數(shù)函數(shù)是f(n) = n * 1 + m * 1拿霉。直接跳過規(guī)則一跷叉。n * 1 + m * 1有兩個變量，
但次數(shù)都是1砌烁，任何一項 n * 1 或 m * 1 都可視為最高價筷转，根據(jù)推導規(guī)則二“保留最高階”姑原，得出
運行次數(shù)函數(shù)是f(n) = n * 1 或 f(n) = m * 1。最后根據(jù)規(guī)則三呜舒，得出code-4的時間復雜度是
f(n) = O(n)锭汛。
對數(shù)階舉例運用
code-5
int count = 1;
while(count < n){
count = count * 2;
//其他時間復雜度為O(1)的代碼
}
code-5似乎不能用前面的推導大O階方法來分析時間復雜度，我從《數(shù)據(jù)結構與算法分析》P21找到了分析
"運行時間中的對數(shù)"的一般法則袭蝗。這個一般法則是：
如果一個算法用常數(shù)時間(O(1)將問題的大小削減為其一部分（通常是1/2）唤殴，那么該算法就是
O(log N)。
另一方面到腥，如果使用常數(shù)時間只是把問題減少一個常數(shù)（如將問題減少1）眨八，那么這種算法就是O(N)。
code-5中左电，假設 n = 8 ，初始化時，while(count < n) 需要運行8次篓足。經(jīng)過一次循環(huán)后段誊，count變?yōu)?，
循環(huán)需要運行4次栈拖，變?yōu)樵瓉淼囊话肓帷８鶕?jù)那條一般法則，判斷 code-5 的時間復雜度是 O(log N)涩哟。
將code-5修改為code-6索赏，
int count = 1;
while(count < n){
count = count + 2;
//其他時間復雜度為O(1)的代碼
}
code-6每次執(zhí)行循環(huán)后，會把問題減少2個常數(shù)贴彼，時間復雜度應為 O(N)潜腻。
若將code-6中的count = count + 2改為code = count - 2，時間復雜度仍然是 O(N)器仗。但我有點理解不了融涣。
平方價舉例運用
code-7
int i, j; /*1*/
for(i = 0; i < n; i++){ /*2*/
for(j = 0; j < n; j++){ /*3*/
//時間復雜度為O(1)的代碼 /*4*/
} /*5*/
} /*6*/
code-7中第二個循環(huán)體的時間復雜度是O(N)。第一個循環(huán)體將第二個循環(huán)體再執(zhí)行N次精钮，時間復雜度變?yōu)?code>O(N2)威鹿。
如果將第二個循環(huán)體中的n改為m，那么code-7的時間復雜度就是O(N*M)轨香。注意忽你，O(N*M)和O(N2)都叫做
平方階，二者實質相同臂容。
多層循環(huán)體的時間復雜度就是每層循環(huán)體的運行次數(shù)相乘科雳。
code-8
int i, j;
for(i = 0; i < n; i++){
for(j = i; j < n; j++){
//時間復雜度為O(1)的代碼
}
}
code-8運行次數(shù)是(n+1)*n*n/2。只保留最高階并且去掉它的系數(shù)策橘，時間復雜度是O(N2)炸渡。有些地方理解不了。
code-9
void function(int count){
int j;
for(j = count; j < n; j++){
printf("%s", "hello,world");
}
}
n++; /* num = 1 */
function(n); /* num = n */
int i,j; /* num = 1 */
for(i = 0; i < n; i++){ /* num = n*n */
function(i);
}
for(i = 0; i < n; i++){ /* num = (n+1)*n/2 */
for(j = i; j < n; j++){
printf("%s", "hi");
}
}
code-9的時間復雜度是多少呢丽已？
首先將每行代碼的執(zhí)行次數(shù)標出來蚌堵。
code-9的執(zhí)行次數(shù)（首先忽略掉常數(shù)項）是n + n*n + (n+1)*n/2，計算結果為1.5*n*n + 2*n沛婴。
只保留最高階1.5*n*n吼畏，最后將系數(shù)變?yōu)?，執(zhí)行次數(shù)為n*n嘁灯，時間復雜度為O(N2)泻蚊。
這種方法有不確定性的因素存在，或者說丑婿，在計算執(zhí)行次數(shù)的時候性雄，使用了互相矛盾的方法没卸。
重新思考之后，發(fā)現(xiàn)并不存在矛盾秒旋，而是《大話數(shù)據(jù)結構》中推導時間復雜度的方法有小缺陷约计。這個推導
本身就是一種粗略估計，為何在推導過程中有時又在進行精確計算呢迁筛？以code-8為例煤蚌，該書使用了精確
的計算方法。若全部都堅持使用粗略估計計算细卧，那么計算過程是這樣的：code-8中第二個循環(huán)體的運行
次數(shù)是N尉桩，或者抽象為“一個變量”，第一個循環(huán)體的運行次數(shù)也是N或M贪庙，也抽象為“一個變量”蜘犁，整體的運行
次數(shù)為兩個變量相乘，即時間復雜度為O(N2)插勤。這種粗略估計計算方法沽瘦，建立的基礎是：影響循環(huán)執(zhí)行次數(shù)
的變量只有那個與循環(huán)終止條件相關的變量，與起始變量無關农尖。
這種方法析恋，又不能適用于對數(shù)階的時間復雜度推導∈⒖ǎ或許助隧，對數(shù)階中的循環(huán)，本來就是一種特殊情況滑沧，不能
采用普通循環(huán)的推導方法并村。此處存疑。*
常見的時間復雜度
直接摘抄《大話數(shù)據(jù)結構》中的有關部分滓技。
理解不了這些時間復雜度所耗時間的順序哩牍，應該如何比較它們所耗時間？
