計算時間複雜度（連續循環）

對於下面的代碼：計算時間複雜度（連續循環）

int func(int x, int y) 
{ 
    int flag=0; 

    for(flag=0; flag<x; flag++) 
    { 
     .... 
    } 

    for(flag=0; flag<y; flag++) 
    { 
     .... 
    } 

    return 0; 
}

以下情況的時間複雜度（我的理解）是 -

x > y => O(x+y) 
y < x => O(x+y) 
x = y => O(2x)

有人可以驗證，如果我是正確的？

謝謝。

來源

2010-12-17 Gong

歡迎來到Stack Overflow！只要你知道，這裏的問題和答案可以格式化，看起來更好，更易於閱讀。您應該在這裏閱讀格式規則，以便您可以設置代碼片段的格式：http://stackoverflow.com/editing-help – 2010-12-17 03:43:39

實際上，由於您沒有使用代碼格式，因此「<」符號後的所有內容都是丟失。所以我們實際上看不到你的代碼:( – 2010-12-17 03:44:30

你是對的.. – Enrique 2010-12-17 03:48:41

x> y => O（x + y） - 是的。但是，如果x = O（y），那麼就是O（x）。

y < x => O（x + y） - 是的。以上同樣的解釋。

x = y => O（2x） - 不完全。您忽略了大O分析中的常數因素。這個想法是，當x變爲無窮大時，'2'或常數將對函數的增長率作出很大貢獻。 O（y^2） - 大O分析的另一個特點是你只考慮主要術語。

大O分析的一個很好的介紹可以在這裏找到一個video講座格式。查看大O分析的第二講。

來源

2010-12-17 04:08:15

大O符號不使用常數乘數。即，沒有O（2n），只有O（n）。這是相對於指數，它是經常可以看到O（2^N）等

你的函數是線性的，因此，如果x == y，然後量級被簡單地列爲O（X ）。

來源

2010-12-17 03:59:39 chrisaycock

計算時間複雜度（連續循環）

回答

相關問題