問題由來是一位非計算機專業的同學初學算法課，在一些虛擬情景下解題非常地頭疼而出現的。
很有意思的是，從回答他的問題中，我也重新思考了一些問題。

Try to create a useful algorithm that takes O(n^2) for the worst case Omega(1) for the best case Theta(log(n)) for the average

當寫到這題的時候，我沒多想就寫了一連串if else，然后往里面填充算法。
可當我試圖引導我同學做這道題時，出現了以下對話

”你怎么會用sorting（分類）的算法呢？“
”為什么不能用sorting啊？“
”因為sorting最快average也要O(Nlog(N))啊。“
”為什么啊？“

于是我給他看了sorting算法的表格。雖然解決了問題，但還是不能解決”為什么“啊。說實話，一開始，我也只是把這算法當做規律給記下來了。為什么sorting就不能更好了呢？是否有更好的方法來證明這個呢？

由于數學公式在segmentfault上還是很難編輯，我這里給一個鏈接好了。

但是似乎還是太復雜了一點，還是死記硬背的把O(Nlog(N))記下來了。

我在想，是否能夠這么思考問題。假設，我們只需要找到數的相同數在一個排序好的N元素的array中，假設我們并不知道這個數是否為哪個特定index上，但必然在array中，那很簡單，最快的average是O(log(N))。其次，我們要找到第二個這樣的數，仍然是O(log(N))。不斷循環這個問題，那最后就出現了O(Nlog(N))的排列，然后，我們將這個組合打亂。實際上是個依次逐步的反向過程。雖然打亂組合顯然沒有必要去一個一個找數。但這個反向過程確是正向過程的最佳方式。（我覺得這兩個過程應該可以用數學證明，可惜現在還沒有這個能力。）

------------------------------------------------------------分割線-------------------------------------------------------------
另一個問題，多大的概率情況下，我們需要開始考慮概率是否會影響算法。
這也是來自同學對話，但我卻非常在意。為什么我們總沒有一個確定性的定義劃分，認為多大的概率可能會影響算法，或者說，直接將概率引進入算法中。例如，在排列好的一組從0到n取出的N個數中，用binary search找到特定數，然后greedy search找重復數。那如果出現n個數都是重復數，這個算法就變成了O（N）。但是出現這個的概率為1/n^N。所以才可以近乎不記。是否應該定義但概率的倒數小于big O的數量級時，認為該算法會受到影響。
------------------------------------------------------------分割線-------------------------------------------------------------
這篇隨筆實在是非常粗淺，本來想把最近自己看的AKS算法和一些并行運算算法的知識介紹一下。但仍然沒能找到一種很好的方式來敘述。最近有可能要參加ACM，所以暫時就這樣吧。

總結

以上是生活随笔為你收集整理的一篇小的随笔，关于记忆算法和概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。