我正在嘗試設計一個時間復雜度為 O(1) 的算法，該算法從不是最小值的數(shù)組中返回一個值。我知道搜索數(shù)組并比較其元素以找到最小的將使算法為 O(n)，因此不起作用。如果我寫一個單獨的方法，使用排序算法先對數(shù)組進行排序，然后返回最小的，這會影響算法的時間復雜度嗎？這是我的代碼：private static int nonSmallestElement(int[] array) { int smallest = smallestElement(array); int index = (int) (array.length * Math.random()); System.out.println("Index = " + index); for (int i = index; i < array.length; i++) { if (array[i] != smallest) { return array[i]; } } return array[1];}private static int smallestElement(int[] array) { Arrays.sort(array); return array[0];}這里的Arrays.sort()方法是使用雙樞軸快速排序算法，它是 O(n log(n))?，F(xiàn)在這是否意味著該nonSmallestElement()方法也具有該時間復雜度，還是 O(1) 因為它不必處理排序？
1 回答
Qyouu
TA貢獻1786條經(jīng)驗 獲得超11個贊
你是對的，你需要計算所有動作來計算算法的復雜性。但是您應該了解規(guī)則，例如較大的包括較小的（更多示例）。在您的情況下，您調用smallestElement()一次 - O(nlogn) 而不是循環(huán) O(n)。結果整體復雜度將是 O(n + nlogn)。但是最終的復雜度nonSmallestElement()是 O(nlogn) 因為 nlogn 更大。
另一方面，不可能有比 O(n) 更好的算法來返回非最小值。因為您需要至少迭代所有元素一次才能找到最小值。異?？梢允桥判驍?shù)組。
從評論更新：
這里有一個提示：如果您手頭有兩個不同的值，那么較大的值一定不是數(shù)組中的最小值。對于“典型”數(shù)組，您希望在任意兩個元素中找到兩個不同的值。@James K Polk
添加回答
舉報
0/150
提交
取消