我需要幫忙計算「大O」

第一個問題;我需要幫忙計算「大O」

sum = 0; 

for i = 1 to n; i++ 
{ 
for j = 1 to i * i; j++ 
    { 
    for k = 1 to j; k++ 
     sum ++; 
    } 
}

和

問題二;

sum = 0; 

for i = 1 to n 
    { 
    for j = 1 to i * i 
    { 
    if j mod i == 0 
     { 
     for k = 1 to j 
      sum ++; 
     } 
    } 
    }

嗨，我在IT新的，我需要幫助（實際上是兩個：d）

我遇到了「大O」前幾天，雖然我正在研究這件事，我發現這個地址，實際上我從這裏學到很多...

但大多數關於「大o」的例子只是爲了解釋它，在這裏我有兩個問題。經過我的計算，我發現第一個大O爲O（n^5），第二個爲O（n^3）。但這些數值過於龐大......

所以我在這裏

，我需要你的幫助......（甚至你可以寫的結果是什麼都沒有解釋，但請幫我對這些問題）

謝謝作爲預先...

來源

2011-03-25 Gokhan Gumus

您可以修復縮進或添加大括號，以便我們知道哪些循環結束於哪裏？ – CanSpice 2011-03-25 23:35:31

家庭作業，也許？ – 2011-03-25 23:42:25

好，大O的定義是一個函數克（x）的是O（F（X））如果克（x）的 ≤ KF（x）的一些常數k。

換句話說，big-O告訴你一個函數增長速度的一些想法;如果它是$ O（n）*，它將與輸入的長度成比例增長。你在計算什麼，以及計算的細節，都隱藏在常量中。

下面是一些例子：

for i from 1 to n { 
    do something 
}

是O（n）的。您每次穿過n項目。

for i from 1 to n { 
} 
for i from 1 to n { 
}

序列

兩次仍O（n）的，因爲你看每個ñ項目的兩倍。這是2n這仍然是O（n）。

在另一方面，

for i from 1 to n { 
    for j from 1 to n { 

    } 
}

是爲O（n 2 ）因爲用於我每個步驟中，你經歷1-正爲Ĵ。

理清你的代碼的縮進，所以我們確定你在做什麼，看看這些例子是否有幫助。

更新

這些都是非常有趣的問題，來想一想它。

的i*i長期

考慮的i*i的值，即，我將是什麼。在最壞的情況下，我== n，所以j是1,4,9,16...(n*n)。 x從1到n是多少x ？（提示：1/6（...）（...），現在你填空。）

的，如果...... MOD長期

時將這個詞是真實的？

來源

2011-03-25 23:44:49

非常感謝您的回答，但讓我迷惑的是;第二個問題的「if」情況和第一個問題的「i * i」情況，這些如何影響「大o」 – 2011-03-25 23:49:39

非常感謝您的答覆，經過一些計算後我改變了主意O（n^7）爲第一種情況，O（n^3）爲第二種情況。我不確定是否是真的，你能否再次幫我（請：D） – 2011-03-29 22:30:24

我需要幫忙計算「大O」

回答

相關問題