有哪些演算法觸及到了問題的最本質的層面？

02-14

包括但不限於物理本質。
最本質的層面，其實是沒法定義的，因為永遠不知道有沒有更本質的層面。但這個問題的原意是，像熱力學定律能量守恆、熵不減、絕對零度，還有參數辨識中的最大似然估計這等這樣的，很難想像出有更fundamental的層面的演算法。

前面有答案提到了在查找演算法中的KMP，但是我覺得那個還是在匹配這個層面。而我給出的bloom filter，則是從結構上碰觸到查找演算法的本質。。一般的哈希演算法是把稀疏的點聚合到一個很小的範圍內，通過選擇代數結構把點分散開。尤其是多哈希結構，類似稜鏡光譜一樣，一束光進去，幾束光出來，分別打在不同的譜線上。普通的哈希追求的是分解出來的光譜結構分散，不同光打進去最好出來的譜線別重合。而bloom filter則是認為，如果打進來的光是不同的，那麼他們不可能一模一樣出現在一組相同的譜線上，否則可以很大可能認為入射光是相同的。第一次看到這個演算法的時候覺得這個演算法很美很直接，類比了一下，知道這個演算法的人應該明白我在說什麼了。

數值積分。。。。

按數學定義，積分就是分劃、求和取極限。而計算機算數值積分就真的是分劃、求和。。。。然後不取極限

============================

我自己覺得這個例子並不好，想起來有更好的會更新

個人認為是分治演算法，這是解決問題的基本模式，如何分解轉化問題，從一個大問題轉化為一個或者多個小問題。

主要兩個部分：

1. 如何分解

2. 分解後小問題的解如何組合生成原問題的解

這兩個部分的不同方案會延伸出不同的演算法

1. 貪心

2. 二分

3. bagging, boosting

4. 快速排序

5. kd tree, r tree

等等等等

這個是從結構(戰略)上。如果從實現(戰術)上，可以延伸出

1. 搜索

2. 記憶化搜索

3. 動態規劃

區別只在於如何平衡存儲和計算，平衡空間和時間

等等

隨機數生成演算法，由於計算機的本質，只要在同樣的環境下，就一定可以復現你以前做的操作，你永遠無法做出真隨機。

對於分析演算法來講，我認為是加法計算。自從把加法弄明白一點門道之後對於初等分析方面的演算法沒有的恐懼感。

剛有人指出這個演算法叫KMP。我查了一下，我指的的確是這個。

--------------------------------

我覺得那個Knuth年輕時做的無回溯模式匹配演算法觸及了問題的本質層面。這個演算法的厲害之處在於，在一個大字串裡面查找小字串的時候，對小字串略加分析，就能使得在查找時指針位置不回溯。

為什麼說它觸及了問題的最本質層面呢？之所以查找子串時會出現「回溯」的現象，本質上是沒有充分利用被查詢字串開頭和結尾的形式。而這個演算法的首先通過分析小字串，把這份有用的信息儲存在了一個數組中。很巧妙。有時間我再補補。

最大似然估計～

牛頓迭代法算么？

搜了下，也沒看見把牛頓迭代法講得特別明白的。

求y的平方根, 只要隨便用一個數不停去迭代x=(x+y/x)/2，就能得到近似解。

在數學裡，這個問題其實就是 $f(x) = x^2-y$ 的曲線和x軸的交點。

從圖上面看就是不停迭代每一個點的切線和x軸的交點，而切線的斜率就是在那個點的導數，交點就不停向結果逼近。(好奇有沒有特別明顯的辦法證明收斂)。所以斜率就可以用這個計算 $frac{f(x_0)-0}{x_0-x_1} = 2x_0$ and $f(x_0) = x_0^2 - y$

所以隨意取個 $x_0$ , 就有:

$\ frac{x_0^2-y}{x_0-x_1} = 2x_0 \ x_0^2-y = 2x_0^2-2x_0*x_1 \ 2x_0*x_1 = x_0^2+y\ x_1 = (x_0+frac{y}{x_0})/2$

神經網路無視【應該說站到了更高一層抽象高度】具體問題從現有數據x y

優化cost function強行得到x到y的函數

超級暴力

身為工科狗來秀下自己的社科修養。

海德格爾在《致人道主義書信》結尾寫到「馬克思的歷史唯物主義已經深入到歷史本質的那一維度當中去了。在我看來，胡塞爾沒有達到這一高度，薩特也沒有達到這一高度。而只有達到了這一高度，才有資格和馬克思主義對話。」

不服的人，我們來算個重積分比比。