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