資訊專欄INFORMATION COLUMN
摘要：時間復(fù)雜度場景一一根長寸的面包，每天吃掉一寸，那么吃完整個面包需要幾天答案自然是天可以記作場景二一根寸的面包，每天吃掉剩余的一半，吃的只剩下寸，需要多少天答案以為底，的對數(shù)，簡寫成，所以為天可以記作場景三每天吃掉一個雞腿，那么吃掉整個雞腿需
時間復(fù)雜度
場景一：一根長10寸的面包，每3天吃掉一寸，那么吃完整個面包需要幾天？
答案自然是：3×10=30天
可以記作：T(n) = 3n
場景二：一根16寸的面包，每5天吃掉剩余的一半，吃的只剩下1寸，需要多少天？
答案：以2為底，16的對數(shù)，簡寫成log16，所以為 5×log16 = 20天
可以記作： T(n) = 5logn
場景三：每2天吃掉一個雞腿，那么吃掉整個雞腿需要多少天？
答案：2天
可以記作：T(n) = 2
場景四：一根長10寸的面包，吃掉第一個一寸需要1天，吃掉第二個1寸需要2天，吃完整個面包需要多少天？
答案：從1累加到10，共55天
可以記作：T(n) = 0.5n^2+0.5n
這四個場景分別是：線性式、對數(shù)式、常量式、多項式
漸進時間復(fù)雜度：比如算法A的相對時間是 T(n)=100n，算法B的相對時間是T(n)=5n^2，到底哪個運行時間長呢？這要看n的取值
官方定義：
若存在函數(shù) f(n)，使得當 n 趨近于無窮大時，T(n)/f(n) 的極限值為不等于零的常數(shù)，則稱 f(n) 是 T(n) 的同數(shù)量級函數(shù)
記作 T(n)=O(f(n)) 稱為O(f(n))為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度，漸進時間復(fù)雜度用大寫 O 表示，所以也被稱為大O表示法
如何推導出時間復(fù)雜度，有如下幾個原則：
如果運行時間是常數(shù)量級，用常數(shù) 1 表示
只保留時間函數(shù)中的最高階項
如果最高階項存在，則省去最高階項前面的系數(shù)
回頭看上面四個場景
| T(n) = 3n | -> | T(n) = O(n) |
| T(n) = 5logn | -> | T(n) = O(logn) |
| T(n) = 2 | -> | T(n) = O(1) |
| T(n) = 0.5n^2+0.5n | -> | T(n) = O(n^2) |
文章：什么是時間復(fù)雜度？
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/96995.html
摘要：為了防止某些文檔或腳本加載別的域下的未知內(nèi)容，防止造成泄露隱私，破壞系統(tǒng)等行為發(fā)生。模式構(gòu)建函數(shù)響應(yīng)式前端架構(gòu)過程中學到的經(jīng)驗?zāi)Ｊ降牟煌幵谟冢饕獙Ｗ⒂谇‘數(shù)貙崿F(xiàn)應(yīng)用程序狀態(tài)突變。嚴重情況下，會造成惡意的流量劫持等問題。 今天是編輯周刊的日子。所以文章很多和周刊一樣。微信不能發(fā)鏈接，點了也木有用，所以請記得閱讀原文~ 發(fā)個動圖娛樂下： 使用 SVG 動畫制作游戲 使用 GASP ...
摘要：基本結(jié)構(gòu)語言中，一個頁面是由四個部分組成文檔聲明標簽對標簽對標簽對圖示文檔聲明這是一個文檔聲明，表示這是一個頁面。標簽標簽表示頁面內(nèi)容的范圍。 HTML HTML ...
摘要：本筆記共四篇源碼閱讀筆記源碼閱讀筆記源碼閱讀筆記服務(wù)器啟動與請求處理源碼閱讀筆記對象起因前兩天終于把自己一直想讀的源代碼讀了一遍。首先放上關(guān)鍵的源代碼在上一篇源碼閱讀筆記服務(wù)器啟動與請求處理中，我們已經(jīng)分析了的作用。 本筆記共四篇Koa源碼閱讀筆記(1) -- coKoa源碼閱讀筆記(2) -- composeKoa源碼閱讀筆記(3) -- 服務(wù)器の啟動與請求處理Koa源碼閱讀筆記(4...
摘要：異步請求線程在在連接后是通過瀏覽器新開一個線程請求將檢測到狀態(tài)變更時，如果設(shè)置有回調(diào)函數(shù)，異步線程就產(chǎn)生狀態(tài)變更事件，將這個回調(diào)再放入事件循環(huán)隊列中。 基礎(chǔ)：瀏覽器 -- 多進程，每個tab頁獨立一個瀏覽器渲染進程（瀏覽器內(nèi)核） 每個瀏覽器渲染進程是多線程的，主要包括：GUI渲染線程 JS引擎線程 也稱為JS內(nèi)核，負責處理Javascript腳本程序。（例如V8引擎） JS引擎線程負...
摘要：舒適的編輯體驗通過語法高亮，最大地消除與生俱來的編輯和閱讀的割裂感。所以，是不是又少了一個回到閱讀模式的借口代碼塊語法高亮通過插件可以支持代碼塊里面的代碼語法高亮，其他的編輯器好像沒有支持。 首發(fā)于簡書. showImg(https://segmentfault.com/img/remote/1460000009164987); 從去年的十一開始到今天，VNote已經(jīng)半周歲了，也迭代到...
閱讀 2336·2021-09-30 09:48
閱讀 3693·2021-09-24 10:27
閱讀 1940·2021-09-22 15:32
閱讀 2101·2021-08-09 13:44
閱讀 3658·2019-08-30 15:55
閱讀 1112·2019-08-29 17:12
閱讀 2143·2019-08-29 17:05
閱讀 2985·2019-08-29 13:43
