戴文渊
2024-04-25 15:12
13次浏览
學習函數極限的時候，會發現要逼近同一個極限的速度，其實對於不同函數來說是不一樣的。比如 y=x 和 y=x^2 ，當x趨於正無窮那會兒，兩者逼近正無窮的速度不一樣，是x的平方更快一點。於是就引出階數的概念，來表示函數趨近極限的快慢。
很明顯，快慢是一個相對的概念，就是說需要函數兩兩比較。有高階和同階兩種。高階的定義是這樣的：
設兩個函數 f(x),g(x) 。她們在某一個x點上（或者x趨於無窮）的極限一樣。
如果存在一個常數 M ，在x趨於同一個極限的過程中，總有 |f(x)|leq M|g(x)| ，就說明 f(x) 比 g(x) 增長得慢，記為 f(x)=O(g(x)) ， g(x) 比 f(x) 高階。
一直有個提問，為什麼 f(x) 比 g(x) 的 M 倍小，就說明整體就比 g(x) 慢。這就要回到定義去，階數講的是趨近極限的速度。極限阿，是不能夠用一個蛐蛐常數就能控制的。如果真有 |f(x)|leq M|g(x)| 成立，那麼根據極限的保不等式性，就會有 | lim (f(x)) |<M |lim(g(x))|sim|lim(g(x))| ，所以就能推出f(x)趨近極限的速度比g(x)小瞭（因為極限都比人傢小瞭）
然後，與階數相關的涉及到瞭計算機科學和算法模塊。
對於計算機來說，由於計算存在一定誤差，所以我們就希望誤差能趨於0，於是就引入瞭誤差趨於0的速度，叫做big O(N)。當然在誤差界都是用 O(h^n) 表示，這是由於計算機裡所有的函數都是用泰勒公式表示的。什麼叫泰勒？就是多項式組成的函數。因此誤差最大也隻有 h^n ，其中 h=x-x_0 ，表示自變量離展開點的距離。我們希望誤差隨著n的變大而越來越小，顯然隻要h小於1，n越大就好。
對於算法來說，有時間復雜度和空間復雜度。其實兩者都是一樣的，隻是維度不同。會有 O(n^k) , O(logn) , O(a^n) 等等，n代表次數，可以是算法時間的累計，也可以是空間的累計，我們自然也是希望復雜度不要那麼大。