【閱讀筆記】——時間復雜度

keithxiaoy 發布于2019-08-23 11:28 / 450人閱讀

摘要：時間復雜度場景一一根長寸的面包，每天吃掉一寸，那么吃完整個面包需要幾天答案自然是天可以記作場景二一根寸的面包，每天吃掉剩余的一半，吃的只剩下寸，需要多少天答案以為底，的對數，簡寫成，所以為天可以記作場景三每天吃掉一個雞腿，那么吃掉整個雞腿需

時間復雜度

場景一：一根長10寸的面包，每3天吃掉一寸，那么吃完整個面包需要幾天？
答案自然是：3×10=30天
可以記作：T(n) = 3n

場景二：一根16寸的面包，每5天吃掉剩余的一半，吃的只剩下1寸，需要多少天？
答案：以2為底，16的對數，簡寫成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

這四個場景分別是：線性式、對數式、常量式、多項式

漸進時間復雜度：

比如算法A的相對時間是 T(n)=100n，算法B的相對時間是T(n)=5n^2，到底哪個運行時間長呢？這要看n的取值

官方定義：

若存在函數 f(n)，使得當 n 趨近于無窮大時，T(n)/f(n) 的極限值為不等于零的常數，則稱 f(n) 是 T(n) 的同數量級函數
記作 T(n)=O(f(n)) 稱為O(f(n))為算法的漸進時間復雜度，簡稱時間復雜度，漸進時間復雜度用大寫 O 表示，所以也被稱為大O表示法

如何推導出時間復雜度，有如下幾個原則：

如果運行時間是常數量級，用常數 1 表示

只保留時間函數中的最高階項

如果最高階項存在，則省去最高階項前面的系數

回頭看上面四個場景


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)

文章：什么是時間復雜度？

GPU云服務器云服務器時間復雜度快速排序時間復雜度最大流算法時間復雜度數據結構時間復雜度

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96995.html

前端閱讀筆記 2016-11-25

摘要：為了防止某些文檔或腳本加載別的域下的未知內容，防止造成泄露隱私，破壞系統等行為發生。模式構建函數響應式前端架構過程中學到的經驗模式的不同之處在于，它主要專注于恰當地實現應用程序狀態突變。嚴重情況下，會造成惡意的流量劫持等問題。今天是編輯周刊的日子。所以文章很多和周刊一樣。微信不能發鏈接，點了也木有用，所以請記得閱讀原文~ 發個動圖娛樂下：使用 SVG 動畫制作游戲使用 GASP ...

KoreyLee 2019-08-20 12:32 評論0 收藏0
學習筆記 | HTML 基本結構和基本標簽 ——前端學習第一步！

摘要：基本結構語言中，一個頁面是由四個部分組成文檔聲明標簽對標簽對標簽對圖示文檔聲明這是一個文檔聲明，表示這是一個頁面。標簽標簽表示頁面內容的范圍。 HTML HTML ...

sPeng 2021-09-30 09:48 評論0 收藏0
Koa源碼閱讀筆記(4) -- ctx對象

摘要：本筆記共四篇源碼閱讀筆記源碼閱讀筆記源碼閱讀筆記服務器啟動與請求處理源碼閱讀筆記對象起因前兩天終于把自己一直想讀的源代碼讀了一遍。首先放上關鍵的源代碼在上一篇源碼閱讀筆記服務器啟動與請求處理中，我們已經分析了的作用。本筆記共四篇Koa源碼閱讀筆記(1) -- coKoa源碼閱讀筆記(2) -- composeKoa源碼閱讀筆記(3) -- 服務器の啟動與請求處理Koa源碼閱讀筆記(4...

ityouknow 2019-08-22 10:34 評論0 收藏0
【筆記】你不知道的JS讀書筆記——異步

摘要：異步請求線程在在連接后是通過瀏覽器新開一個線程請求將檢測到狀態變更時，如果設置有回調函數，異步線程就產生狀態變更事件，將這個回調再放入事件循環隊列中。基礎：瀏覽器 -- 多進程，每個tab頁獨立一個瀏覽器渲染進程（瀏覽器內核）每個瀏覽器渲染進程是多線程的，主要包括：GUI渲染線程 JS引擎線程也稱為JS內核，負責處理Javascript腳本程序。（例如V8引擎） JS引擎線程負...

junnplus 2019-08-22 15:43 評論0 收藏0
靡不有初，鮮克有終——寫在VNote半周歲

摘要：舒適的編輯體驗通過語法高亮，最大地消除與生俱來的編輯和閱讀的割裂感。所以，是不是又少了一個回到閱讀模式的借口代碼塊語法高亮通過插件可以支持代碼塊里面的代碼語法高亮，其他的編輯器好像沒有支持。首發于簡書. showImg(https://segmentfault.com/img/remote/1460000009164987); 從去年的十一開始到今天，VNote已經半周歲了，也迭代到...

roland_reed 2019-06-28 10:21 評論0 收藏0