分析我的程序的時間複雜度

我在確定算法的時間複雜性方面存在問題。分析我的程序的時間複雜度

for(int i=0;i <n i++){} O(n) 

for(int i= 0 ;i<n ;i++){ O(n^2) 
    for(int j=0;j<n;j++){ 

    } 
}

現在對於下面的代碼什麼的複雜性

for(i =0; i<n ; i++) {} 
for (j=0;j<n ;j++) {}

是O（2N），因爲它invloves 2個獨立的循環？

如果我開始j = 5到n怎麼辦？

來源

2011-03-11 jslearner

沒有O(2n)，它只是O(n)。換句話說，它以與n增加相同的比例進行縮放。

如果這是一個嵌套循環，這將是O(n²)但你{}空塊的存在意味着它沒有嵌套。

不管你是從一個還是五個開始都沒有區別，它仍然與n一致，只是稍微有一個負值不變的加法。因此仍然是O(n)。

複雜度O(n),O(cn)和O(n+c)（其中c是常數）都是等價的。另外，您通常也只使用效果最好的術語。

所以你通常不會看到O(7n³ + 3n² + 12n + 2)，這將簡化爲O(n³)。

來源

2011-03-11 06:37:50 paxdiablo

最終的結果是，通過一些我不記得的花式數學，你可以把2n變成大O（n）。這些係數被認爲是常數，因爲我們關心的是複雜性，當單獨處理這個問題時，您需要檢查導致最大增長的方程的部分。在這種情況下，大O（n^2）是方程複雜性中最主要的因素。因此，你的算法被認爲是Big O（n）。

我的道歉，基於誤讀最後幾行代碼的小錯字。你詢問的是大O（n）

來源

2011-03-11 06:34:12

上午位混淆我從想到得到爲（I = 0; I jslearner 2011-03-11 06:37:28

是的，它是O（2n），但它與O（n）相同，因爲乘以常數在漸近複雜性中無關緊要。同樣，如果跳過五個第一個元素，則循環需要O（n-5）個時間，但這與O（n）相同，因爲加上或減去一個常數比乘以常數還要弱。見例如http://en.wikipedia.org/wiki/Big_O_notation的定義。

來源

2011-03-11 06:36:56

有沒有這樣的事情O（2n）。時間複雜度是指一個算法如何擴展到無窮大，而不是實際的運行時間。在你的例子中，你有兩個線性[O（n）]時間的循環，這意味着它們將隨着輸入線性縮放，因此你的整體算法是O（n）。

如果您啓動j = 5，它仍然是O（n），因爲它仍然線性縮放。

所以實質上，O（2n）== O（n）。

來源

2011-03-11 06:40:16

有時間，其適用的複雜性兩個重要的規則，當且僅當n的值非常大...

高階項的coeffeicient可以忽略不計。
所有低階項都可以被忽略。

爲什麼這些假設是非常簡單的，突然想到考慮一個例子： -

假設時間複雜度爲5N^2 + 3N。在非常低的n值時，係數和低階項在n的小變化中顯着。但假設n的值非常大，則低階項對時間複雜度的影響非常小，而且最高階項的係數也可以以相同的方式忽略。

注意時間複雜性只有在n在理論上接近無窮大時才起主要作用。

來源

2011-03-11 06:45:04 NirmalGeo

希望你現在很清楚，我不能找到我讀到這裏的來源。我有一個相同的疑問，並在文章中明確提到了時間複雜度對大值N的影響和重要性。 – NirmalGeo 2011-03-11 06:57:06

時間複雜度在'n'獲得任何地方之前很長時間內扮演着非常重要的角色_near_ infinity :-)否則，我們根本就不在乎。 – paxdiablo 2011-03-12 14:58:07

複雜性是描述關係輸入n和時間的函數形狀的度量。

請記住，在大多數情況下，您不知道常數並不是不變的原因。如果您比較兩個可比較的算法，則可以使用常量，但在大多數情況下，您會引用一般的複雜度，並測量輸入n的時間。在你的情況下，O（2 * n）和2 * O（n）是一樣的，這只是O（n），因爲2 * O（n）沒有那麼多，並且可以用常數2來比較。算法。說第二個算法具有複雜性2 * O（n）沒有太大意義。

用這種方式看複雜性。

可以說你有n =一百萬的算法。什麼是操作次數的近似大小或爲了

O(n)   -> 1e6 and this can be calculated in most cases 
O(n * log(n)) -> 2*1e7 this can also be calculated in reasonable time. 
O(n^2)   -> 1e12 you will not be able to compute whit this algorithm in reasonable time 
O(n^3)   -> 1e18 here are so many operations that you have to think twice on how you are going to aproach this problem

來源

2011-03-11 07:15:19

分析我的程序的時間複雜度

回答

相關問題