在我的作業中，我必須實作一個演算法，具體細節并不重要，但我無法對這個特定演算法的時間復雜度有一個明確的答案。
簡而言之，它看起來像這樣：
for(let i = 0; i < 3; i ) {
for(let j = 0; j < n - 1; j ) {
for(let k = 0; k < 8; k {
// Do some stuff
}
}
}
這個演算法的時間復雜度是多少？
一開始我以為它會像O（n ^ 3）一樣。但我想得越多，我就越覺得它實際上更像是一個 0(n)。因為，即使我們有 3 個 for 回圈，也只有一個可以是可變大小的，另外兩個是不變的。
那么這個演算法的實際時間復雜度是多少呢？是 O(n^3)、O(n) 還是別的什么？
uj5u.com熱心網友回復：
是的，會的O(n)。你說的對。
執行的總數是3 * n * 8 = 24*n24 可以忽略 large的地方n。所以復雜度是O(n)
uj5u.com熱心網友回復：
直接回答
除了已經給出了很好的答案之外，我希望您能夠描繪每個回圈的計算：
應用的某些隱含規則是相對于：
- 常數k的復雜度為
O(1)
示例：3 = O(1),8 = O(1)
- 給定變數n 和常數k 的高值，驗證關系：
O(n k) = O(n) k = O(n)
例子： O(n-1) = O(n) -1 = O(n)
- 給定變數n 和常數k 的高值，驗證關系：
k x O(n) = O(kn) = O(n)
例子： 3x O(n) = O(3n) = O(n)
延期
讓我們改變你的回圈，讓你有O(n^3)你想知道的情況：
for(let i = 0; i < n-1; i ) {
for(let j = 0; j < n - 1; j ) {
for(let k = 0; k < n-1; k {
// Do some stuff
}
}
}
因為每個回圈的復雜度為 O(n)，我們有O(n) x O(n) x O(n) = O(n^3)
uj5u.com熱心網友回復：
代碼的時間復雜度為O(n)：
由于外層回圈的迭代次數是恒定的，因此其內層回圈每次迭代n - 1次數，并且對于這些時間中的每一次，最內層回圈的迭代次數都是恒定的。
因此，您得到3 * (n - 1) * 8 = 24n - 24并且由于常量被丟棄為大 O 表示法，您得到O(n).
話雖如此，代碼的時間復雜度可能會受到在最內層回圈（即// Do some stuff部分）內部運行的代碼的影響。如果您只在那里執行恒定數量的操作，則代碼復雜性不會受到影響。但是，例如，如果您在其中對大小為 n 的陣列進行排序，那么這會將時間復雜度更改為n * nlogn。
uj5u.com熱心網友回復：
此代碼的時間復雜度為O(n). 外回圈和內回圈具有恒定的迭代次數，并且獨立于輸入大小 ( n)。對于大 O 表示法，常量會被丟棄。
uj5u.com熱心網友回復：
時間復雜度將是O(n)，因為 3 和 8 是可以忽略的常數。此外，第二個回圈是 until n - 1，其中 1 也被忽略。注意：所有這些對常量的無知都是n在價值變得非常大的時候。
如果在所有這些回圈中呼叫了一個函式，則對該函式的總呼叫為n，但精確的總呼叫將是
(8 * 3 * n) - ((8 * 3) - 1)
我們在大 O 表示法中忽略了它。
試試這個代碼C：
#include <stdio.h>
size_t my_calls = 1;
void call_me(void){
my_calls = 1;
}
int main(void)
{
size_t n = 1000; // let n = 1000
for(size_t i = 0; i < 3; i )
{
for(size_t j = 0; j < n - 1; j )
{
for(size_t k = 0; k < 8; k )
{
call_me();
}
}
}
printf("Total calls %lu\n", my_calls);
if(my_calls == (8 * 3 * n ) - ((8 * 3) - 1))
printf("GOOD\n");
else
printf("BAD\n");
return 0;
}
LIVE DEMO
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/434662.html