/ taohigo.com / 0浏览

階數

學習函數極限的時候,會發現要逼近同一個極限的速度,其實對於不同函數來說是不一樣的。比如 y=xy=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代表次數,可以是算法時間的累計,也可以是空間的累計,我們自然也是希望復雜度不要那麼大。

同工同酬!昆明經濟技術開發區招聘教師182人
選調生總結2022.6.27 褪去“書生氣”,沾滿“泥土香”
選調生總結2022.6.27 褪去“書生氣”,沾滿“泥土香”
4000字深度剖析 | “一書三證”的前世今生
4000字深度剖析 | “一書三證”的前世今生
我的傢庭史
瓢蟲
瓢蟲
谷神不死——牛匕·《老子》古典新解

0

  1. This post has no comment yet

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注