算法的大O分析？

這似乎是基於關歸併的搜索算法。它用於一個有序數組。大O的複雜性仍然是O（n log n）？算法的大O分析？

public static boolean fastSearch(int[] data, int min, int max, int target) 
{ 
    int N = data.length; 
    boolean found = false; 
    int midpoint = (min+max)/2; // determine the midpoint 

    if (data[midpoint] == target) { 
      found = true; 
    } else { 
      if (data[midpoint] > target) { 
       if (min <= midpoint - 1) { 
        // Recursion on the left half of the array 
        found = fastSearch(data, min, midpoint-1, target); 
       } 
      } else { 
       if (midpoint + 1 <= max) { 
        // Recursion on the right half of the array 
        found = fastSearch(data, midpoint+1, max, target); 
       } 
      } 
    } 
    return found; 
}

這是我自己的分析我沒有，我只是想確認我是否正確與否：

每次通過數據加倍小節的大小。這些需要重複加倍直到找到目標。它需要log（n）加倍，並且數據的每次傳遞都與項目的數量成正比。所以，它是O（n log n）。

來源

2013-11-26 user3037881

可以請你縮進代碼，並加括號？我正在努力成爲一名人類編譯器。 – PaulProgrammer

「，並且數據的每次通過與項目的數量成比例」。你確定嗎？ :) – Guido

如果這是[二進制搜索]（http://en.wikipedia.org/wiki/Binary_search_algorithm）的實現，則運行時間應該是'O（log n）'。這就是說，我不能說這是基於你的格式的正確實施。 –

這看起來像一個正常的二進制搜索算法對我來說，這是衆所周知的有O(log n)複雜性（除非它返回值是否被人發現，而不是它的位置）。你基本上「訪問」最多log n陣列的條目：

首先您訪問並在中間檢查點，檢查其一個你尋找，如果不是
，你限制你搜索到「低「或」高「尋求部分陣列，
因此，您將桌子分成兩半，然後只選擇其中一個部分，只剩下一個元素（最糟糕的情況 - 尋找的元素會早一點找到），
你可以多少次這樣做呢？ n/2/2/2/2/.../2 = 1 - 的/2量將log n。

這不是一個嚴格的分析。有可能是一些關閉的情況的一個錯誤，以及無邊界條件檢查，但最終的結果肯定是O(log n)。

當然，我們不得不假設data數組排序和n = max - min（和min < max）。否則，這將是垃圾。

順便說一句：f(n) = O(log n)意味着log n（從某個點）是f(n)的一種上限（可能有一些正的常數因子）。 f(n) = O(n log n)意味着對於n log n也是如此。所以是的，如果它受log n的限制，它肯定會受到n log n的限制（因爲對於所有n個更大的N爲f(n) <= c1(log n) <= c2(n log n)），但這不是你正在尋找的答案。

來源

2013-11-26 19:20:37

算法的大O分析？

回答

相關問題