怎樣計算/證明/目測 出解決一個問題的最低時間複雜度？

就是直覺上 我感覺每個問題 都有一個最低時間複雜度 無論採用什麼演算法解決問題 都無法突破這個限制

那麼怎麼知道 解決某個問題的演算法的最低時間複雜度是什麼呢？

我有一個很模糊的想法 就是：這個演算法不去做多餘的計算 因為輸入數據的信息量肯定都大於輸出數據的信息量 所以每一步都儘可能扔掉一些信息 只留下對結果有決定性意義的信息（即計算結果）去進行下一步計算

---

如果你知道了這麼一個方法...

別忘了告訴我:

資訊理論能給出一些簡單問題的下界:

比較排序:

非比較排序:

還有各類數據結構:

頂多有些圖論問題也有最優複雜度的證明吧,也就僅此而已了

我記得最近計算幾何里有個最優演算法突然被抽出來證明是錯的來著...

---

更複雜的問題我認為是難以判定的

搞不好甚至是不可判定問題

考慮到更多的問題是不可計算問題

複雜果然是世界的本質啊&>&>逃

---

這是一個異常困難的事情。對於大部分有意義的問題， 是一個下界，也就是演算法必須完整地讀一遍輸入。但是除此以外，人們幾乎不知道任何更好的下界。即便是3-SAT這樣目前已知的最好的演算法是指數級的問題，仍然沒有一個 的下界（m是輸入的3-CNF的長度）。也就是說，理論上根據目前已知的事實，甚至仍然可能存在一個 的演算法。

不過另一方面，對於很多數據結構問題，大家還是知道一些證明最低複雜度的方法的。比如這個Partial Sum問題：維護一個長度為n的數組，每次操作可以修改其中一個數，也可以詢問前k個數的和(k是詢問的輸入)，用線段樹可以做到每次操作 log n 的複雜度，同時這篇論文（http://people.csail.mit.edu/mip/papers/sums/sums.pdf 中的Section 3）證明了任何數據結構都不可能做到 。

---

演算法導論上似乎有介紹這個問題

首先要明確的概念是，只要可以證明不存在比這條界線更優的演算法，那麼它就是一個下界，解決任何問題的時間複雜度都有無數多的下界。比如0就可以是任何問題的下界，因為不會有演算法需要花比0更少的時間了。

要證明「正確」的那個下界，也就是所有下界中最高的那個，一般來說有兩步，首先證明它是一個下界，然後找到一個上界與它相等的演算法。

至於怎麼找，通用的辦法肯定是不可能存在的，因為，像上面某個答案說的，P和NP是不是相等人類都還不知道呢。

一種辦法是，如果是基於比較的問題，可以用資訊理論加決策樹來找到一個(未必是最優的)下界，基本思路就是先找出為了得到最終答案需要的信息，然後把這些信息的所有可能狀態算出一個排列數，最後用決策樹一次比較可以排除一半，所以對排列數取一個對數就得到一個下界了。

另一種辦法叫potential function，基本思路就是你找到一個隨著計算過程單調減的變數(一般是某種你需要知道的信息的數量)，並且這個變數歸零的時候你就能得到答案，算出它的初始值，然後算出每步計算可以減小這個變數的值的上界，兩者相除，就得到時間複雜度下界了(同樣未必是最優的)。

---

首先你並沒有搞清楚演算法是什麼，從你的話可以提煉出以下幾點：

1. 有沒有衡量一個演算法的臨界點，我認為答案是有，但是不可知。演算法是人類智慧的結晶，隨著時代的進步，同一問題的演算法也在進步，排序演算法發展了冒泡排序，插值排序，堆排序，快速排序等等演算法，用的時間和空間越來越少，也許未來還會有更逆天的演算法，但我們沒有辦法去預測。

2. 不做多餘事情的演算法。事實上衡量一個演算法的好壞，不僅近是時間複雜度，還要考慮空間複雜度，只不過人對時間感知比較敏感，而空間又可以靠硬體去提升，所以衡量一個演算法往往以時間複雜度為標準。就拿排序演算法來說，桶排序的時間複雜度為n，可以說相當優秀了，快排也比不上它，但是實際情況中卻很少使用，除了因為它的局限性比較大，另一點原因就是它的空間複雜度很糟糕，實際生產環境中要考慮到硬體成本，桶排序佔用的內存過高所以使用很少。回到主題，任何一個合格的演算法都不會做多餘的事情，如果有要麼演算法不合格，要麼是為了用時間換空間或者空間換時間，所以不存在做多餘事情的演算法。

3. 演算法的輸入數據一定大於輸出數據，我不知道這句話從何而來，演算法必備的五個條件是：可行性、確定性、有窮性、輸入、輸出。沒有你說的輸入大於輸出。例子很常見，輸出前100位斐波那契序列，輸入只有100這個數字，輸出卻有100個數字。

4. 執行過程中扔掉一些信息，保留有用的。其實句話跟第一句話類似，同認為演算法做了多餘的事情，但我還是單獨把這句話拿了出來，因為我想你可能問的是內存優化的問題，其實這個就是空間複雜度，通俗點說就是演算法執行過程中需要多少的額外內存空間，這些空間哪裡來的呢？可能是一些臨時變數。我不知道時間複雜度的最小值，但我知道空間複雜度的最小值，那就是1，或者稱為原地空間，演算法除了輸入數據的佔用不會再開闢其它內存，或者開闢的內存與數據量無關，它是一個常數。還是以排序演算法為例，數字排序一般會用到交換，常見的交換兩個數字：

int temp = a;

a = b;

b = temp;

這裡的temp就是佔用的額外內存，但我如果這麼寫（我只是舉個例子，不要因為可能溢出噴我）：

a += b;

b = a - b;

a -= b:

我同樣完成了數字交換，也沒有開闢新的內存，但是我多做了幾次加法運算，我記得加法運算應該比賦值運算浪費時間，所以這是用時間去換空間。

綜上所述，題主的問題其實是對演算法的本質不夠了解，產生了曲解，建議再好好看看演算法導論，補習一下相關知識。

---

這不就演算法與數據結構前幾章的內容嗎，你仔細讀讀。

---

演算法和數據結構有關，巧妙的演算法是不受最低複雜度限制的。

---

推薦閱讀：