時間復(fù)雜度和空間復(fù)雜度

O表達的是 它的復(fù)雜度是n的怎樣一個函數(shù)

時間復(fù)雜度 ：

公式 ： T(n) = O( f(n) ) f(n) 表示每行代碼執(zhí)行次數(shù)之和，而 O 表示正比例關(guān)系
1.O(1) : 常數(shù)復(fù)雜度
2.O(log n) 對數(shù)復(fù)雜度 如二分查找
3.O(n) 線性時間復(fù)雜度 如二叉樹遍歷，前序，中序，后續(xù)
4.O(n^2) 平方 冒泡排序
5.O(n^3) 立方
6.O(2^n) 指數(shù)
7.O(n!) 階乘

1.O1:無論代碼執(zhí)行了多少行，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)，那這個代碼的時間復(fù)雜度就都是O(1)
2.O(n): for循環(huán)里面會執(zhí)行n遍代碼，消耗的時間隨著n的變化而變化。所以用O(n)標識
3.O(n^2)：O(n)的代碼在循環(huán)一遍，兩個for

空間復(fù)雜度

1.如果代碼里又數(shù)組，數(shù)組長度就是空間復(fù)雜度。一維數(shù)組空間復(fù)雜度為傳入元素的個數(shù)。如果是二維數(shù)組，數(shù)組長度為n平方，空間復(fù)雜度為n平方。
2.如果是遞歸，遞歸最深深度，就是空間復(fù)雜度。