時間複雜度

那些年邊罵學了沒用，邊努力學習的東西，現在一件一件的給了我回報。

1. 什麼是時間複雜度？

時間複雜度是指程序運行從開始到結束所需要的時間。為了便於比較同一個問題的不同演算法，通常做法是，從演算法中選取一種對於所研究的問題來說是基本操作的原操作，以該基本操作重複執行的次數做為演算法的時間量度。基本操作應是其重複執行次數和演算法時間成正比的原操作，多數情況下它是最深層循環內的語句中的操作。

在進行演算法分析時，語句總的執行次數T(n)是關於問題規模n的函數，進而分析T(n)隨n的變化情況並確定T(n)的數量級。時間複雜度一般記作：T(n)= O(f(n))。

2. 時間複雜度計算方法

時間複雜的推導方法一般如下:

第一步：用常數1取代運行時間中的所有加法常數。

第二步:在修改後的運行次數函數中，只保留最高階項。

第三步:如果最高階項存在且不是 1，則去除與這個項相乘的常數。

常用的時間複雜度所耗費的時間從小到大依次是：O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

3. 產品設計的抽象化

產品可能有的功能多種多樣，可能的布局千差萬別，可能的交互方式更是多如牛毛。如何找到個好的方法把產品功能在一個界面良好的組織起來，是一件困難的事情。

我們需要首先把產品抽象成幾個維度：

所有的產品都可以抽象為用戶維度+內容維度+狀態維度。三個維度互相穿插影響時，會產生不同的複雜度。這時，可以用時間複雜度的方式來評判產品設計的合理性。

4. 實例分析：對比手Q和微信消息界面

大家可以對比查看手Q和微信的消息界面。用戶的維度，微信只有一種，而手Q有普通用戶、會員用戶、超級會員用戶、體驗會員用戶等。內容維度，微信有用戶消息、群聊消息、公眾號消息，而手Q有用戶消息、群聊消息、服務號、系統消息、新聞消息等，甚至還加入了QQ電話（這個讓複雜度大大提高了）。狀態維度，微信由正常態、未點擊態、紅點態，手Q還多了群消息的幾種狀態（這裡微信做得很特別，把單聊和群聊做成了一致）。

這樣子，微信用戶去遍歷內容時的複雜度是O(n)，因為用戶維度已經最簡化；而手Q用戶去遍歷內容時的時間複雜度至少是O（n^2），甚至是O（n^3）。這時，你可能會深刻體會到微信為什麼不做會員體系，為什麼群組設計跟單聊模式基本一致。

用時間複雜度去評判手Q和微信時，我都會感慨，這兩個產品做的都太牛叉了。微信承擔如此強大的功能屬性，卻能將整個產品設計得時間複雜度最低，基本都是線性的。手Q則是添加了如此多的功能的前提下，也能採取一個良好的布局將功能擺放盡量合理。

大家可以再去對比看看微信、手Q的更多細節，比如通訊錄、發現、空間等。你能發現微信真的很可怕，幾乎把各個地方的時間複雜度都控制在線性階；手Q也很可怕，功能做得比微信多三倍，但也基本能找到合適的布局。相比來說我更喜歡基本將時間複雜度優化到極致的微信，甚至能夠在某些非常複雜的跳轉邏輯中做好優化將時間複雜度降低，膜拜之。