>[success] # 復雜度分析 ~~~ 1.首先要掌握一個數據結構與算法中最重要的概念——復雜度分析 ~~~ >[info] ## 大 O 復雜度表示法 ~~~ 1.概念：算法的「執行時間」與每行代碼的「執行次數」成正比'T(n) = O(f(n))', 其中T(n)表示算法執行總時間，f(n)表示每行代碼執行總次數，而n往往表示數據的規模。 1.1.'T(n)' -- 算法執行總時間 1.2.'f(n)' -- 表示每行代碼執行的次數總和 1.3.'n' -- 數據的規模的大小 2.大O符號（Big O notation）是用于描述函數漸進行為的數學符號。更確切地說， 它是用另一個（通常更簡單的）函數來描述一個函數數量級的漸近上界,舉個例子： 'T(n) = 4n^2 - 2n + 2,當 n 增大時，n^2; 項將開始占主導地位，而其他各項可以被忽略' 上面的內容就可以表示為'T(n)=O(4n^2)' 理解：就是O 可以理解我們默認一個常量無窮大的時候，只關心他的主導條件，忽略其他與它 相比可以忽略的條件 -- 也就是無窮大漸近 ~~~ >[danger] ##### 通過代碼案例理解(一) ~~~ 1.下面代碼是前端的代碼，代碼實現的是累加求和。 ~~~ ~~~ function cal(n) { let sum = 0 // 運行時間 1 個unit_time let i = 1 // 運行時間 1 個unit_time for(;i<=n;i++){ // 運行時間 n 個unit_time sum = sum + i // 運行時間 n 個unit_time } return sum } console.log(cal(10)) // 55 ~~~ * 分析這段代碼的復雜程度 ~~~ 1.參數'n'對應 -- 上面概念講解里的 '數據的規模的大小' 2.把每行運行時間默認為 1 個unit_time 3.像上面的代碼'i' 和 'sum' 都是變量，只會執行一次因此它倆的時間效率分別都是1 個unit_time ，for循環的時間效率是根據'n'的長度來決定的因此是 n 個unit_time 4.所以上面的代碼總時長是 '2*unit_time+n*unit_time+n*unit_time'整理可得： (2n+2)*unit_time 5.用大 O 復雜度表示法，取'無窮大漸近'T(n) = O(n) ~~~ >[danger] ##### 通過代碼案例理解(二) ~~~ 1.分析下面案例，主要分析的是內層循環代碼，因為我們都知道外層循環一次等于內層循環 一遍，因此下面代碼中的外層次數是'n',外層每循環一次內層就給來一遍因此內層循環次數就是 'n*n' 2.整理一下，下面代碼的執行時間 '3*unit_time + 2n*unit_time +2n^2unit_time'合并可得： 'T(n) = (2n2+2n+3)*unit_time' 3.用大 O 復雜度表示法，取'無窮大漸近'T(n) = O(n^2) ~~~ ~~~ int cal(int n) { int sum = 0; // 1 個unit_time int i = 1; // 1 個unit_time int j = 1; // 1 個unit_time for (; i <= n; ++i) { // n 個unit_time j = 1; // n 個unit_time for (; j <= n; ++j) { // n^2 個unit_time sum = sum + i * j; // n^2 個unit_time } } } ~~~ >[danger] ##### 簡單總結 ~~~ 1.所有代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比 2.大 O 時間復雜度實際上并不具體表示代碼真正的執行時間，而是表示 代碼執行時間隨數據規模增長的變化趨勢，所以，也叫作'漸進時間復雜度' 簡稱'時間復雜度' 3.當 n 很大時公式中的低階、常量、系數三部分并不左右增長趨勢，所以都可以忽略。 我們只需要記錄一個最大量級就可以了，如果用大 O 表示法表示剛講的那兩段代碼的 時間復雜度，就可以記為：T(n) = O(n)； T(n) = O(n^2),這是大O符號的在數學中的含義 無窮大 ~~~