非大O複雜度

算法複雜度的計算讓我非常困惑。對於一項任務，我們給出以下功能並要求找出其複雜性。非大O複雜度

int selectkth(int a[], int k, int n) { 
    int i, j, mini, tmp; 
    for (i = 0; i < k; i++) { 
     mini = i; 
     for (j = i+1; j < n; j++) 
     if (a[j]<a[mini]) 
      mini = j; 
     tmp = a[i]; 
     a[i] = a[mini]; 
     a[mini] = tmp; 
    } 
    return a[k-1]; 
}

分配本身會詢問到「尋找用於查找整數的無序陣列的第k個最小整數的函數的複雜性。」

此外我們被要求寫我們的f函數以及我們的g函數。

據我所知，對於f函數，我會在函數中添加所有的賦值和操作。我在這個f函數中包含變量k或n嗎？作爲最佳猜測，我會說f（n）= 6n + 4（n^2），因爲在循環的第一個循環中有6個循環操作，接下來是嵌套循環中的4個操作。

爲了進一步理解，這個函數的大O複雜度是O（n^2）嗎？我說因爲有一個嵌套的for循環，這意味着每次都會遇到每個項目的最壞情況。

我很抱歉，如果我不清楚。我很困惑這是如何工作的。

來源

2014-10-09 wpaverd

你是正確的，兩個嵌套的循環意味着'爲O（n^2）'，海事組織試圖拿出一個公式來表示的確切數目指令是一個傻瓜的差事，因爲有些將成爲多個CPU指令，有些將由編譯器進行優化。 – IllusiveBrian 2014-10-09 02:50:51

兩個嵌套循環不一定意味着'O（n^2）'。這裏外環從0到k-1，這可能導致'O（kn）'而不是'O（n^2）'。（我說「可能」是因爲我猜測沒有形式證明。）重要的是要精確地處理變量，而不是總是將自己的思維過程簡化爲「兩個循環=二次方= O（n^2）」。 – 2014-10-09 02:52:24

內循環執行'（n-1）+（n-2）+ ... +（n-k）'次，顯然是'O（kn）'。 – 2014-10-09 04:01:07

這裏去一個簡單的分析：

外環做k迭代。

Inter loop正在做n-1迭代，但它的確如此k次。

因此，我們有O(k*(n-1)) = O(kn-k) 由於k可以等於n（我們可以問第n的最小整數數組中的）的表達becames O(n*n-n) = O(n^2-n) = O(n^2)。

有關大O符號符號更多的幫助，請上網：http://web.mit.edu/16.070/www/lecture/big_o.pdf

來源

2014-11-24 04:17:00

回答

相關問題