所以首先讓我談談這個問題的動機。假設您必須在陣列中找到最小值和最大值。在這種情況下，您可以通過兩種方式進行操作。
第一個包括迭代陣列并找到最大值，然后做同樣的事情來找到最小值。這個解是 O(2n)。
第二個是只迭代陣列一次并同時找到最小值和最大值。這個解是 O(n)。
即使時間復雜度減半，對于 O(n) 解決方案的每次迭代，您現在有兩倍多的指令（??忽略編譯器如何優化這些指令），所以我相信它們應該花費相同的時間來執行.
讓我給你舉第二個例子。現在你需要反轉一個陣列。同樣，您有兩種方法可以這樣做。
第一個是創建一個空陣列，遍歷填充空陣列的資料陣列。這個解是 O(n)。
第二個是遍歷資料陣列，交換第 0 個和第 n-1 個元素，然后交換第 1 個和第 n-2 個元素，依此類推（使用此策略），直到到達陣列的中間。這個解是 O((1/2)n)。
同樣，即使時間復雜度減少了一半，每次迭代的指令數也增加了三倍。您正在迭代 (1/2)n 個元素，但對于每次迭代，您必須執行三個 XOR 指令。如果您不使用 XOR，而是使用輔助變數，您仍然需要多 2 條指令來執行變數交換，所以現在我相信 o((1/2)n) 實際上應該比 o(n) 差。
說完這些，我的問題如下：
忽略空間復雜性、垃圾收集和編譯器可能的優化，我可以假設有 O(c1*n) 和 O(c2*n) 演算法，以便 c1 > c2，我可以確定給我 O(c1 *n) 與給我 O(c2*n) 的那個一樣快還是更快？
這個問題很酷，因為它可以對我從這里開始撰寫代碼的方式產生影響。如果“更復雜”(c1) 的方式與“不太復雜”(c2) 的速度一樣快但更具可讀性，我會堅持使用“更復雜”的方式。
uj5u.com熱心網友回復：
c1 > c2，我能確定給出 O(c1 n)的演算法與給出O(c2 n)的演算法一樣快或更快嗎？
整個問題在于“快”或“更快”這兩個詞。計算復雜度并沒有嚴格衡量我們直觀理解的“快速”。不涉及數學細節（盡管這是一個好主意：https : //en.wikipedia.org/wiki/Big_O_notation），它回答了“當我的輸入增長時它會變慢的速度有多快”的問題。因此，如果您有 O(n^2) 復雜度，您可以大致預期將輸入的大小加倍會使您的演算法花費 4 倍的時間。而對于線性復雜度，2 倍大的輸入只會使時間加倍。正如你所看到的，它是相對的，所以任何常數都會抵消。
總結一下：從你提出問題的方式來看，大 O 符號似乎不是這里的正確工具。
uj5u.com熱心網友回復：
根據定義，如果c1和c2是常數，O(c1*n) === O(c2*c) === O(n)。也就是說，長度陣列的每個元素的操作數n在這種復雜性分析中完全無關。
它會告訴你的只是“它是線性的”。也就是說，如果您對長度為 1 的陣列進行了 1 次無數次操作n，那么對于一個長度陣列2*n（加上或減去比線性增長慢的東西），您將有 2 次無數次的操作。
我可以假設有 O(c1 n) 和 O(c2 n) 演算法以便 c1 > c2，我可以確定給我 O(c1 n)的演算法與給我 O 的演算法一樣快或更快嗎？ (c2 n)？
不，一點也不。
首先，因為該分析中的常量毫無意義。沒辦法說：這與您設定的任何限制c1和c2大 O 分析完全無關。整個想法是它將放棄這些限制。
其次，因為它們沒有告訴您任何可以讓您比較兩種演算法運行時的特定值n.
這種復雜性分析只能讓您比較演算法的漸近行為。現實世界的問題一般不關心漸近線在哪里。
假設這A1(n)是演算法 1 輸入長度所需的運算元n，與A2(n)演算法 2 相同。您可能有：
A1(n) = 10n 900A2(n) = 100n
兩者的復雜度都是O(A1) = O(A2) = O(n)。對于小輸入，A2 更快。對于大輸入，A1 更快。他們改變的點是n == 10。
這個問題很酷，因為它可以對我從這里開始撰寫代碼的方式產生影響。如果“更復雜”(c1) 的方式與“不太復雜”(c2) 的速度一樣快但更具可讀性，我會堅持使用“更復雜”的方式。
不僅如此，還有一個事實是，當您有 2 種不同的演算法實際上屬于不同的復雜度類別（例如，線性與二次）時，使用更高復雜度的演算法可能仍然有意義，因為它可能仍然更快。
例如：
A3(n) = n^2A4(n) = n 10^20.
例如，演算法 3 是二次的，而演算法 4 是線性的，但它具有恒定的巨大初始化時間。
達約的規模投入n == 10^10，這將是更快地使用二次演算法。
很可能您的特定問題的所有相關輸入都在該范圍內，這意味著二次演算法將是更好、更快的選擇。
底線是：為了分析在給定輸入（或給定的輸入有界范圍，因為幾乎所有現實世界問題）上運行演算法所需的實際時間，并將其與另一種演算法進行比較，大O分析是沒有意義的。
另一種說法是：您在問一個實用的“工程”問題（即哪個選項更好/更快），但試圖用僅對“理論”分析有用的工具來回答問題。那個工具很重要，是的。但它沒有機會通過設計為您提供您正在尋找的答案。
uj5u.com熱心網友回復：
根據定義，時間復雜度忽略常量。所以O((1/2)n) == O(n) == O(2n) == O(cn)。
您的示例O((1/2)n)說明了為什么會這樣，因為常量可以衡量任何單位，因此比較它們毫無意義。
您永遠無法僅根據時間復雜度來判斷哪種演算法更快。但是，當 n 接近無窮大時，您可以判斷哪個更快。由于常數從時間復雜度中洗掉，它們將被視為相等，因此即使 n 接近無窮大O(c1n)，O(c2n)您仍然無法分辨哪個更快。
uj5u.com熱心網友回復：
（我的理論計算機科學課程是幾十年前的）
O(cn) 是 O(n)。
它仍然是對陣列的線性搜索。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/371793.html