具有這種結構的遞回函式的時間復雜度是多少
void f(int n)
{
if (n == 0)
return;
for (int i = n; i >= 1; --i)
{
// something O(1)
f(n - i);
}
}
我的想法是它遵循
T(n) = T(0) ... T(n-2) T(n-1) = (T(0) ... T(n-2)) T(n-1) = T(n-1) T(n-1) = 2T(n-1)
所以我們會說 O(2^n-1)？
或者是
T(n) = T(0) * ... * T(n-1)
uj5u.com熱心網友回復：
你的分析似乎是正確的。
如有疑問，您可以測量它。如果復雜性確實如此，O(2^n)那么您可以計算內部回圈執行的頻率，并增加n計數除以2^n應該收斂：
#include <iostream>
struct foo {
int counter = 0;
void f(int n) {
if (n == 0)
return;
for (int i = n; i >= 1; --i) {
counter;
f(n - i);
}
}
};
int main() {
for (int i=0;i < 4; i) {
long int n = 2<<i;
foo f;
f.f(n);
std::cout << n << " " << (2<<n) << " " << f.counter / static_cast<double>(2<<n) << "\n";
}
}
輸出是：
2 8 0.375
4 32 0.46875
8 512 0.498047
16 131072 0.499992
請注意，此測量不能證明您的分析是正確的。盡管計數似乎收斂到0.5并且測量不能偽造您的分析。計數似乎在某個地方2^n-1，只是對于復雜性而言，常數因子2無關緊要，您可以將其寫為O(2^n).
PS：在考慮演算法時，復雜性很有趣。在考慮具體實作時，情況會有所不同。請注意，撰寫的函式可以優化為等效void f(int) {}的，顯然不是O(2^n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/470933.html
上一篇：如何檢查程式cout是否為空？