給定代碼的時間複雜度。

下面的代碼是查找一個數字在數組中顯示的次數。例如：給定代碼的時間複雜度。

1,2,2,2,3,4,5,5,5,5 number 2 = 3 times number 5 = 4 times.

什麼是下面的代碼Java中的時間複雜度？解決時間複雜性問題的最佳方法是什麼？

public static void main(String[]args) 
    { 
     int[] data = {1,1,2,3,4,4,4,5,6,7,8,8,8,8}; 
     System.out.println(count(data,8)); 


    } 


public static int count(int[] a, int x) 
{ 
    int count=0; 
    int index=0; 
    while(index<a.length) 
    { 
     if(a[index]==x) 
     { 
      count++; 
     } 
     index++; 

    } 
    return count; 
}

來源

2013-01-06 user1952556

你正在迭代整個數組一次，所以我猜想它是O（N）。 – Blender

請修正你的符號。 'O（n）'和'o（n）'不是一回事。從某種意義上說，它們是對方的對立面。見http://en.wikipedia.org/wiki/Big_O_notation – NPE

我正在看代碼上面的例子：你是否試圖找到排序數組中所有重複項的出現次數？ – jlordo

是o（n），logN還是其他？

你看每一個元素曾經那麼它是O（n）

如果是O（N），我可以我可以做LOGN共謀這項任務？

做一個低值和高值的二進制搜索，搜索值小於您搜索的值和剛纔的值。這兩個結果之間的差異會告訴你有多少。這是一個O（日誌N）搜索。

來源

2013-01-06 09:43:05

那麼，如果他需要檢查每個元素，那就是N * log（N）。 – nullpotent

@iccthedral正確。技術上我會說O（M * log N）其中M是數字的範圍。除非有大量重複，否則如果需要計算所有元素，則不會執行此操作。 –

while(index<a.length)

這個循環中運行data每一次價值。這是O（n）。如果您想在O（日誌n）中執行此操作，您將需要一個排序數組和二進制搜索。你有一個有序的數組，所以你只需要做一個二進制搜索。

來源

2013-01-06 09:42:34 Mike

答案是O（n）。

您在每個索引處遍歷數組。

例如數組大小是10 - > 10比較，數組大小是100 - > 100比較等等。

來源

2013-01-06 09:42:43 jlordo

您檢查數組中的每個元素，因此您的代碼具有時間複雜度O(n)。

要在O(log n)時間這樣做，您必須利用數組排序的事實。這可以通過binary search的變體完成。由於這看起來像功課，所以在提供更多提示之前，我會先讓你考慮一下。

來源

2013-01-06 09:42:46 NPE

O（n） 此代碼使用數組中的每個元素。

while(index<a.length)

可以更換它

for(int index = 0; index < a.length; i++)

來源

2013-01-06 09:44:42 Leo

爲O（n）。當通過每個代碼迭代和陣列的每個元素，其0（n）的。

來源

2013-01-06 10:17:12

給定代碼的時間複雜度。

回答

相關問題