1.算法復雜度

• 談算法不談復雜度=耍流氓
• 在實現之前，我們要預估算法所需要的資源
  時間：基本操作次數（匯編指令條數）
  空間：占用內存字節(jié)數
  區(qū)別：空間可以再利用

• O(1)
  基本運算，＋，－，＊，／，%，尋址
• O(logn)
  二分查找
• O(n^1/2)
  枚舉約數
• O(n)
  線性查找
• O(n²)
  樸素最近點對
• O(n³)
  Floyd最短路
  普通矩陣乘法
• O(nlogn)
  歸并排序
  快速排序的期望復雜度
  基于比較排序的算法下界
• O(2ⁿ)
  枚舉全部的子集
• O(n!)
  枚舉全排列
• 總結：
  優(yōu)秀 O(1) < O(logn) < O(n^1/2) < O(n) < O(nlogn)
  可能可以優(yōu)化 O(n²) < O(n³) < O(2ⁿ) < O(n!)

2.從暴力算法開始優(yōu)化

2.1 Leetcode 121

Best Time to Buy and Sell Stock

2.2 最大子數組和

給定數組a[1…n]，求最大子數組和，即找出1<=i<=j<=n，使a[i]+a[i+1]+…+a[j]最大。

2.2.1 暴力枚舉 O(n3)

2.2.2 優(yōu)化枚舉 O(n2)

2.2.3 貪心法 O(n)

2.2.4 總結

3.思考題

3.1 設計一個隊列

支持：出隊，入隊，求最大元素
要求O(1)
均攤分析

3.2 判斷是否構成三角形

給定一個正整數組a，是否能以3個數為邊長構成三角形？
即是否存在不同的i，j，k，
滿足 a[i] < a[j] + a[k]
并且 a[j] < a[i] + a[k]
并且 a[k] < a[i] + a[j]

3.3 Leetcode 152 Maximum Product Subarray

參考

• 1）面試求職 第四期