這是將數字取冪為給定冪的代碼：
#include <stdio.h>
int foo(int m, int k) {
if (k == 0) {
return 1;
} else if (k % 2 != 0) {
return m * foo(m, k - 1);
} else {
int p = foo(m, k / 2);
return p * p;
}
}
int main() {
int m, k;
while (scanf("%d %d", &m, &k) == 2) {
printf("%d\n", foo(m, k));
}
return 0;
}
如何計算函式的時間復雜度foo？
我已經能夠推斷出，如果k是 的冪2，則時間復雜度是O(log k)。
但我發現很難計算k. 任何幫助將非常感激。
uj5u.com熱心網友回復：
如何計算函式 foo() 的時間復雜度？
我已經能夠推斷出，如果 k 是 2 的冪，則時間復雜度為 O(logk)。
首先，我假設每個函式呼叫所需的時間是恒定的（例如，如果乘法所需的時間取決于被相乘的數字，則情況并非如此——在某些計算機上就是這種情況）。
我們還假設k>=1（否則，函式將無限運行，除非發生溢位）。
讓我們將值k視為二進制數：
如果最右邊的位為0(k%2!=0為假)，則數字右移一位 ( foo(m,k/2)) 并遞回呼叫該函式。
如果最右邊的位是1(k%2!=0為真)，則該位更改為0( foo(m,k-1)) 并遞回呼叫該函式。（我們還沒有看這個案子k=1。）
這意味著該函式對每個位呼叫一次，并且對每個位呼叫一次1。或者，換句話說：0對數字中的每個位呼叫一次，對每個位呼叫兩次1。
如果N是函式呼叫次數，n1是1位數，n0是0位數，我們得到以下公式：
N = n0 2*n1 C
常量C( C=(-1)，如果我沒記錯的話) 代表了k=1我們迄今為止忽略的情況。
這意味著：
N = (n0 n1) n1 C
而且 - 因為n0 n1 = floor(log2(k)) 1：
floor(log2(k)) C <= N <= 2*floor(log2(k)) C
如您所見，時間復雜度始終為O(log(k))
uj5u.com熱心網友回復：
O(log(k))
添加了一些修改以輸出電子表格圖的統計資訊。
#include <stdio.h>
#include <math.h>
#ifndef TEST_NUM
#define TEST_NUM (100)
#endif
static size_t iter_count;
int foo(int m, int k) {
iter_count ;
if (k == 0) {
return 1;
} else if(k == 1) {
return m;
} else if (k % 2 != 0) {
return m * foo(m, k - 1);
} else {
int p = foo(m, k / 2);
return p * p;
}
}
int main() {
for (int i = 1; i < TEST_NUM; i) {
iter_count = 0;
int dummy_result = foo(1, i);
printf("%d, %zu, %f\n", i, iter_count, log2(i));
}
return 0;
}
```C
Build it.
```Bash
gcc t1.c -DTEST_NUM=10000
./a > output.csv
現在使用電子表格程式打開輸出檔案并繪制最后兩個輸出列。
uj5u.com熱心網友回復：
對于正數，如果是2 的 - 次方k，則函式foo遞回呼叫自身。如果不是 的冪，則遞回呼叫的次數嚴格低于的最大冪的指數。pkpk22 * pp2k
這是一個演示：
讓我們在這種情況下擴展遞回呼叫k % 2 != 0：
int foo(int m, int k) {
if (k == 1) {
return m;
} else
if (k % 2 != 0) { /* 2 recursive calls */
// return m * foo(m, k - 1);
int p = foo(m, k / 2);
return m * p * p;
} else { /* 1 recursive call */
int p = foo(m, k / 2);
return p * p;
}
}
呼叫的總數是floor(log2(k)) bitcount(k)，并且bitcount(k)是按構造<= ceil(log2(k))。
代碼中沒有回圈，每個單獨呼叫的時間都受一個常數的限制，因此總體時間復雜度為O(log k)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/430168.html