問題是：給定一個2n個整數的數組，你的任務是將這些整數分組為n對整數，比如（a1，b1），（a2，b2），...，（an，bn），這使得從1到n的所有i的min（ai，bi）之和盡可能大。提供的解決方案如下：public class Solution { public int arrayPairSum(int[] nums) { int[] arr = new int[20001]; int lim = 10000; for (int num: nums) arr[num + lim]++; int d = 0, sum = 0; for (int i = -10000; i <= 10000; i++) { sum += (arr[i + lim] + 1 - d) / 2 * i; d = (2 + arr[i + lim] - d) % 2; } return sum; }} 我認為說時間復雜度是O（n）是不公平的。雖然 O（n+K） K = 20001 是一個常數，似乎可以省略，但 n 也小于 K。如果是這樣，為什么我不能說時間復雜度是O（1）？
1 回答
繁星淼淼
TA貢獻1775條經驗 獲得超11個贊
對于 ALL n，漸近復雜度測量為 n 的函數。我們關心的是當n變大時會發生什么。真的，真的很大。
也許在實踐中，n將永遠很小。好。
但是，當你為算法給出一個復雜性度量時，根據定義，你是在說隨著n的增長會發生什么。并且不斷增長。當它發生時，它將使K相形見絀。
所以O（n）是的。
澄清：
的確，問題規范說：
n 是一個正整數，在 [1， 10000] 的范圍內。
數組中的所有整數都將在 [-10000， 10000] 的范圍內。
但請記住，這只是針對這個問題！給出硬編碼 K 值的解決方案。正如你所注意到的，這里使用的算法確實應該寫成O（n + K）。這個K不是一個常數因子，可能不應該被刪除。
然而，對于漸近復雜性（Big-O，Big-Theta等），即使使用任意但有限的K，您仍然可以找到常量k和N，使得對于所有n>N，kn>該算法中所需的運算次數，這就是Big-O定義。這就是為什么你會看到很多人說O（n）。
希望有所幫助。
添加回答
舉報
0/150
提交
取消