漸近記號【算法導論筆記】

作者: 執迷_4869 | 来源:发表于2020-01-15 17:20 被阅读0次

漸近記號【算法導論筆記】
讀書報告
（代發）15天構建時間管理系統02-03課程筆記by曉舞蝶
雜項---我為什麼要寫“黃帝內經”讀書筆記
匆匆歲月，給你留下了什麼？
2016年12月8日星期四農曆十一月初十
筆墨讀書——讀通札記（504）
5.31 無錫莎莎愛他美1+採購記
兴庆游记
讀書筆記|讓靈感源源不絕的7個習慣與筆記術

在涉及算法的文章中，常常提到時間複雜度。例如，冒泡排序的時間複雜度是 $O(n^2)$ 。這其實說的是在最壞的情況下，冒泡排序的運行時間的函數 $f(n) < cn^2$ ，其中，c是正常數。
上面使用的符號 $O$ 是一種“漸近記號”。各種漸近記號如下表所示。

記號	公式	含義
$\Theta$	$\Theta(g(n)) = \left\{f(n)\|存在c_1, c_2, n_0 > 0使得對於所有的n \geq n_0，0\leq c_1 g(n) \leq f(n) \leq c_2 g(n)\right\}$	$g(n)是f(n)的漸近緊確界$
$O$	$O(g(n))=\left\{f(n)\|存在c, n_0>0使得對於所有的n \geq n_0，0\leq f(n) \leq cg(n)\right\}$	$g(n)是f(n)的漸近上界$
$\Omega$	$\Omega(g(n))=\left\{f(n)\|存在c, n_0>0使得對於所有的n \geq n_0 ，0 \leq cg(n)\leq f(n)\right\}$	$g(n)是f(n)的漸近下界$
$o$	$o(g(n))=\left\{f(n)\|對任意的c>0，存在n_0 > 0，使得對於所有的n\geq n_0，0\leq f(n)<cg(n) \right\}$	$g(n)是f(n)的非漸近緊確的上界$
$\omega$	$\omega(g(n))=\left\{f(n)\|對任意的c>0，存在n_0 > 0，使得對於所有的n\geq n_0，0\leq cg(n) < f(n)\right\}$	$g(n)是f(n)的非漸近緊確的下界$

參考：
Thomas H. Cormen 《算法導論》原書第三版，殷建平譯

漸近記號【算法導論筆記】
在涉及算法的文章中，常常提到時間複雜度。例如，冒泡排序的時間複雜度是。這其實說的是在最壞的情況下，冒泡排序的運行時...
讀書報告
賴建國。《五經導論》。香港：天道書樓有限公司，2011。創世記部分(頁 83-190)。這本《五經導論》是作者多...
（代發）15天構建時間管理系統02-03課程筆記by曉舞蝶
感謝曉舞蝶為大家提供的《助你連接宏觀與微觀的頂級時間管理系統》課程的思維導圖筆記內容，大家可以參考筆記進行複習。
雜項---我為什麼要寫“黃帝內經”讀書筆記
我為什麼要寫讀書筆記？我為什麼要用繁體字寫讀書筆記？我為什麼要先從“黃帝內經”讀書筆記開始？當下，讀寫書筆記是奢...
匆匆歲月，給你留下了什麼？
已經不記得是何時留下的筆記～
2016年12月8日星期四農曆十一月初十
我還是喜歡用手和筆來記日記。
筆墨讀書——讀通札記（504）
讀中華點校本《卷四十九》，感：1、筆墨讀書。人言：不動筆墨不讀書；再言：好記性不如爛筆頭；更有，孔子《論語》曰：學...
5.31 無錫莎莎愛他美1+採購記
客戶要求：每一盒採購需要實拍記號，願意支付其餘記號費用，10元/張
兴庆游记
早上在床上，翻閱自己一年來的文章，那些遊記、牢騷和隨筆，漸覺興起。遂欲造訪興慶公園。記得去年，文學社諸友曾一同遊...
讀書筆記|讓靈感源源不絕的7個習慣與筆記術
這三年來開始研究筆記議題，也推出自己的課程筆記力最近給了自己一個功課，研讀十本跟筆記相關的書藉，希望能夠有新的筆...