大廠算法面試之leetcode精講2.時間空間復雜度
視頻教程（高效學習）:點擊學習
目錄：
什么時間復雜度
時間復雜度是一個函數(shù)，它定性描述該算法的運行時間，在軟件開發(fā)中，時間復雜度就是用來方便開發(fā)者估算出程序運行時間，通常用算法的操作單元數(shù)量來代表程序消耗的時間，這里默認CPU的每個單元運行消耗的時間都是相同的。假設(shè)算法的問題規(guī)模為n，那么操作單元數(shù)量便用函數(shù)f(n)來表示，隨著數(shù)據(jù)規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率呈現(xiàn)一定的關(guān)系，這稱作為算法的漸近時間復雜度，簡稱時間復雜度，記為 O(f(n))，其中n指的是指令集的數(shù)目。
什么是大O
大O用來表示算法執(zhí)行時間的上界，也可以理解為最差情況下運行的時間，數(shù)據(jù)量和順序等情況對算法的執(zhí)行時間有非常大的影響，這里假設(shè)的是某個輸入數(shù)據(jù)用該算法運行的時間，比其他數(shù)據(jù)的運算時間都要長。
插入排序的時間復雜度我們都說是O(n^2) ，但是插入排序的時間復雜度和輸入數(shù)據(jù)有很大的關(guān)系，假如輸入數(shù)據(jù)是完全有序的，則插入排序的時間復雜度是O(n)，假如輸入的數(shù)據(jù)是完全倒序的，則時間復雜度是O(n^2)，所以最壞是O(n^2) 的時間復雜度，我們說插入排序的時間復雜度為O(n^2)。
快速排序是O(nlogn)，快速排序的在最差的情況下時間復雜度是O(n^2) ，一般情況下是O(nlogn)，所以嚴格從大O的定義來講，快速排序的時間復雜度應該是O(n^2)，但是我們依然說快速排序的時間復雜度是O(nlogn)，這是業(yè)內(nèi)默認的規(guī)定。
二分查找的時間復雜度是O(logn)，每次二分數(shù)據(jù)規(guī)模減半，直到數(shù)據(jù)規(guī)模減少為 1，最后相當于求2的多少次方等于n，相當于分割了logn次。
歸并排序的時間復雜度是O(nlogn)，自頂而下的歸并，從數(shù)據(jù)規(guī)模為n分割到1，時間復雜度是O(logn)，然后不斷向上歸并的時間復雜度是O(n)，總體時間復雜度是O(nlogn)。
樹的遍歷復雜度一般是O(n)，n是樹的節(jié)點個數(shù)，選擇排序時間復雜度是O(n^2)，我們會在對應的章節(jié)逐步分析各個數(shù)據(jù)結(jié)構(gòu)和算法的復雜度。更多的時間復雜度分析和推導可參閱主定理。
分析復雜度的一些規(guī)則
多個時間復雜度相加，如果都是與n相關(guān)，則取取復雜度高的那一個，例如：O(nlogn + n) = O(nlogn)，O(nlogn + n^2) = O(n^2)。
多個時間復雜度相加，如果其中有些項的復雜度和n不相關(guān)則不能忽略任何項，例如：O(AlogA + B)，O(AlogA + B^2)
兩個循環(huán)依次執(zhí)行，則取復雜度高的那個，嵌套多個循環(huán)則需要累乘復雜度。
常見時間復雜度：
-
O(1):常數(shù)復雜度
let n = 100;
-
O(logn):對數(shù)復雜度
//二分查找非遞歸 var search = function (nums, target) { let left = 0, right = nums.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (nums[mid] === target) { return mid; } else if (target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } return -1; };
-
O(n):線性時間復雜度
for (let i = 1; i <= n; i++) { console.log(i); }
-
O(n^2)：平方
for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { console.log(i); } } for (let i = 1; i <= n; i++) { for (let j = 1; j <= 30; j++) { //嵌套的第二層如果和n無關(guān)則不是O(n^2) console.log(i); } }
-
O(2^n)：指數(shù)復雜度
for (let i = 1; i <= Math.pow(2, n); i++) { console.log(i); }
-
O(n!)：階乘
for (let i = 1; i <= factorial(n); i++) { console.log(i); }
常見數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)操作的時間復雜度
遞歸的時間復雜度
遞歸的時間復雜度和遞歸的深度有關(guān)
//遞歸了n層 時間復雜度O(n)
function sum2(n) {
if (n === 0) {
return 0;
}
return n + sum2(n - 1);
}
//二分查找 遞歸了logn層 O(logn)
var search = function (nums, target) {
return search_interval(nums, target, 0, nums.length - 1)
};
function search_interval(nums, target, left, right) {
if (left > right) {
return -1
}
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {//判斷目標值和中間元素的大小
return mid
} else if (nums[mid] < target) {//遞歸尋找目標元素
return search_interval(nums, target, mid + 1, right)
} else {
return search_interval(nums, target, left, mid - 1)
}
}
//斐波那契數(shù)：遞歸法求斐波那契數(shù)，總共遞歸了n層，二叉樹的高度是n，由我們的基礎(chǔ)知識可以知道，
//一個高度為n的二叉樹最多可以有 2^n - 1 個節(jié)點，也就是遞歸過程函數(shù)調(diào)用的次數(shù)，所以時間復雜度為 O(2^n)。
//我們可以看到遞歸樹中包涵非常多的重復計算。
//0, 1，1，2，3 ...
var fib = function (N) {
if (N == 0) return 0;
if (N == 1) return 1;
return fib(N - 1) + fib(N - 2);
};
時間復雜度優(yōu)化
- 采用更好的算法：舉例：1+2+3...n從
1～n求和，直接循環(huán)法，for i->n: sum+=i ，我們也可以用求和公式:n(n+1)/2。在比如有些問題可以用二分查找等。 - 空間換時間，時間是寶貴的，我們計算一個非常耗時的任務(wù)，可能要等上很久，突然的斷電，或者意外情況可能會導致非常大的損失，空間是廉價的，最多我們購買更大內(nèi)存的服務(wù)器，花錢就可以解決，在后面的章節(jié)有非常多的這樣的例子，比如用
set或map加快查找的速度，用二叉搜索樹或者字典樹加快字符串的搜索。
一個時間復雜度分析的例子
有一個字符串數(shù)組，將數(shù)組中的每個字符串按照字母排序，然后在將整個字符串數(shù)組按照字典順序排序。求整個操作的時間復雜度。
假如我說時間復雜度是O(n*nlogn + nlogn) = O(n^2logn) 對嗎，花時間思考一下。
我們來分析一下，假設(shè)最長字符串的長度是s，數(shù)組中有n個字符串，對每個字符串排序 O(slogs)，將數(shù)組中的每個字符串按照字母排序O(n * slogs)，將整個字符串數(shù)組按字典排序 O(s * nlogn)，所以最后的時間復雜度是O(n * slogs) + O(s * nlogn) = O(nslogs + nslogn) = O(ns * (logs+logn))
空間復雜度
空間復雜度指的是算法在運行過程中所占存儲空間的大小，空間復雜度(Space Complexity)記作S(n) ，依然使用大O來表示。利用程序的空間復雜度，可以對程序運行中需要多少內(nèi)存有個預先估計。
常見的空間復雜度
- 一維數(shù)組空間，如果存儲了n個元素，空間復雜度
O(n) - 二維數(shù)組空間，總共有n個數(shù)組，每個數(shù)組存儲了n個元素，空間復雜度
O(n^2) - 常數(shù)空間復雜度
O(1)
遞歸的空間復雜度
//O(1)
function sum1(n) {
let ret = 0;
for (let i = 0; i <= n; i++) {
ret += i;
}
return ret;
}
//O(n)，遞歸了n層，遞歸?？臻g是O(n)的復雜度
function sum2(n) {
if (n === 0) {
return 0;
}
return n + sum2(n - 1);
}
//O(logn)，遞歸了logn層，遞歸棧空間是O(logn)的復雜度
var search = function (nums, target) {
return search_interval(nums, target, 0, nums.length - 1)
};
function search_interval(nums, target, left, right) {
if (left > right) {
return -1
}
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {//判斷目標值和中間元素的大小
return mid
} else if (nums[mid] < target) {//遞歸尋找目標元素
return search_interval(nums, target, mid + 1, right)
} else {
return search_interval(nums, target, left, mid - 1)
}
}
