陣列算法及其時間複雜度分析

我應該分析這段代碼並說出它的時間複雜度，但是我無法理解代碼本身的作用，它如何改變數組a？陣列算法及其時間複雜度分析

我也不明白以下兩個操作： 1）foobar [a [i]] ++; 所以，你用數組a中的元素替換foobar中的零？但是++能做什麼？

2） a [outPos ++] = 1; 這首先增加了outPos，並在整個for循環中保持[0]不變？

public static void foo(int[] a, int b) { 
    int [] foobar = new int[b+1]; 
    for (int i = 0; i<foobar.length; i++) 
     foobar[i]=0; 
    for (int i = 0; i<a.length; i++) 
     foobar[a[i]]++; 
    int outPos = 0; 
    for (int i=0; i<foobar.length; i++) 
     for (int j=0; j<foobar[i]; j++) 
      a[outPos++]=i; 
}

就時間複雜度而言，我認爲它是O（n^2）。前兩個for循環在恆定時間內運行。但是，第三個嵌套循環的最壞情況在我看來，foobar中的最後一個元素很大，然後它會是二次的？

來源

2016-03-04 user260710

這看起來像一個counting sort實現。考慮到N（項數）是數組a的長度，並且M（最大可能項）是b，其時間複雜度是O（N + M）。

來源

2016-03-04 00:23:15 user3707125

它是Counting Sort一實現中，

凡a[]存儲陣列進行排序和b是a[]

foobar[]的最大整數是計數排列的大小b

設的N = sizeof(a), M = b爲通用符號，

前兩個循環：

初始化計數陣列爲零O(M)
計數的元素，說，如果有3「10在a[]，foobar[10] = 3，O(N)

棘手的第三環：

外循環，毫無疑問，O(M)
內循環，你必須考慮總共（最大）j可以增加的時間總數：這就是Sum(foobar[]) = sizeof(a) = N，所以在整個外循環迭代過程中，確實這個循環，最多被執行N次。所以兩個循環作爲一個整體O(N+M)，而不是直觀地O(NM)

所以總的複雜性：O(N) + O(M) + O(N+M) = O(N+M)。如果

一個提示你找到了第三個循環的複雜性是很難理解，認爲這樣的方式：

這是一個0和遊戲。如果有一些foobar[z] is large，那麼有很多foobar[j] = 0這幾乎意味着跳過這樣的i的內部循環。否則，所有foobar[j]將在平均大小左右。

每次迭代i都很難分析，但很容易分析整個內部循環，因爲我們知道foobar[]的總和是一個常數。

來源

2016-03-04 01:55:01 shole

陣列算法及其時間複雜度分析

回答

相關問題