時間復雜度分析 · 數據結構

### 概述 * O(1) * O(n) * O(lgn) * O(nlogn) * O(n^2) 簡單(不是嚴格的意義)大O描述的是算法的運行時間和輸入數據之間的關系. 大O翻譯成中文應該叫做**漸進時間復雜度**.漸進表現在"描述n趨近于無窮的情況" ### O(n)的時間復雜度底下這個例子的時間復雜度是O(n)的,為什么說它是O(n)的呢?n是nums中的元素個數. 這個算法運行的時間大小是和nums中元素呈線性關系的. 這個線性關系就表現在這個n是一次方,它不是O(n方),O(n立方)的. 為什么要用大O,叫做O(n)? 因為它忽略了很多常數 . 實際時間**T = c1*n + c2** ~~~ public static int sum(int[] nums) { int sum = 0; for(int num : nums) sum += num; return sum; } ~~~ * T = 2*n + 2 //O(n) * T = 2000*n + 10000 //O(n) 不要看這個數值很大,它也是O(n)的 * T = 1*n*n+0 //O(n^2) 描述n趨近于無窮的情況 * T = 2*n*n + 300n + 10 //O(n^2) 300n低階項被忽略掉,因為當n趨近于無窮的時候,這個低階項起到的作用太小了 ### 分析動態數組的時間復雜度 #### 添加操作通常在分析的時候要考慮最壞的情況來進行分析 * addLast(e) //O(1) * addFirst(e) //O(n) * add(index e) //O(n/2) = O(n) 嚴格計算需要一些概率論知識 #### 刪除操作 * removeLast(e) //O(1) * removeFirst(e) //O(n) * remove(index,e) //O(n/2) = O(n) * resize() //O(n) #### 修改操作 * set(index,e) //O(1) #### 查詢操作 * get(index) //O(1) * contains(e) //O(n) * find(e) //O(n) ### 分析動態數組操作 * 增 : O(n) * 刪 : O(n) * 改 : 已知索引O(1);未知索引O(n) * 查 : 已知索引O(1);未知索引O(n)