時間復雜度是學習演算法的基石，今天我們來聊聊為什么要引入時間復雜度，什么是時間復雜度以及如何去算一個演算法的時間復雜度
一、刻畫演算法的運行時間
某日，慧能叫來了一塵打算給他補習補習一下基礎知識，只見克寫了一段非常簡單的代碼
一塵看老師有點生氣，開始虛心請教了
為了方便討論，這里我們把每一條陳述句的執行時間都看做是一樣的，記為一個時間單元
① 藍色框的兩條陳述句，花費兩個時間單元
②黑色框的一條陳述句，花費n+1個時間單元
③紅色框的兩條陳述句，花費2*n個時間單元
這不是數學嗎，一塵心里想到
其中的n被我們稱為問題的規模，其實就是你處理問題的大小
慧能順手畫了這個函式的圖
本文主要討論問題規模和運行時間的關系，假定不同輸入和運行時間基本無關
二、時間復雜度
比如說：T(n)=3n+3, 當n非常大的時候常數3和n的系數3對函式結果的影響就很小了
比如：
T(n)=n+1 忽略常數項 T(n)~n
T(n)=n+n^2 忽略低階項 T(n)~n^2
T(n)=3n 忽略最高階的系數 T(n)~n
還好不用掌握那頭疼的數學，一塵心中想到
一塵把話題又拉了回來
更準確地說O代表了運行時間函式的一個漸進上界，即T(n)在數量級上小于等于f(n)
三、時間復雜度的計算
一、得出運行時間的函式 二、對函式進行簡化
①用常數1來取代運行時間中所有加法常數
②修改后的函式中，只保留最高階項 ③如果最高階項存在且不是1，則忽略這個項的系數
O(1)也被稱為常數階
一塵隨手寫了一段嵌套回圈的代碼
接著，慧能又寫了一段時間復雜度為對數的代碼
一向數學不太好的一塵此時有點懵
總結
演算法的學習，第一步就是得先知道啥是時間復雜度，啥是空間復雜度，其實你懂了時間復雜度，也就懂了空間復雜度，建議各位還在校的小伙伴，一定要把資料結構和演算法這門課學好，
無論是面試還是提升自己的內容，演算法學習基本少不了，我這里給大家推薦一份某 BAT 大佬總結的 Leetcode 刷題筆記：BAT 大佬分類總結的 Leetcode 刷題模版，助你搞定 90% 的面試
另外，帥地也把排序演算法系列文章用漫畫寫好了，這里直接貼出鏈接吧，你們負責收藏就好了，嘿嘿，不過這里只給出了 7 種必須掌握的排序演算法，像桶排序，基數排序這些，了解即可，后期也會寫出來滴，
漫畫：什么是冒泡排序演算法？
漫畫：什么是選擇排序演算法？
漫畫：什么是插入排序演算法？
漫畫：什么是希爾排序演算法？
漫畫：什么是歸并排序演算法？
漫畫：什么是快速排序演算法？
漫畫：什么是堆排序演算法？
當然，也歡迎大家來帥地的個人網站玩耍：https://www.iamshuaidi.com，從 0 到 1 總結了帥地的個人學習，
作者簡潔
作者：大家好，我是帥地，從大學、自學一路走來，深知演算法，計算機基礎知識的重要性，公眾號「帥地玩編程」10萬粉絲作者，專業于寫這些底層知識，提升我們的內功，帥地期待你的關注，和我一起學習，點擊了解我四年大學學 習之路 轉載說明：未獲得授權，禁止轉載
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280695.html
標籤：其他