(ainusers原创) 时间复杂度/空间复杂度(初学小结)

时间复杂度(分析算法执行效率【次数】)

1.一层for循环

for(int i=0;i<n;i++){}                                   //n+1

----->时间复杂度：O(n+1)

2.两层for循环

for(int i=0;i<n;i++){ //n+1 for(int j=0;j<n;j++){} //n(n+1)}

----->时间复杂度：O(n^2+2n)或者O(n^2)   （两个答案的原因：常数可省略[并非主要算法影响因素]）

3.特殊情況（递归【递归总次数*每次递归次数】）

int guiMethod(int n){ if(n==1) return n; return guiMethod(n-1)}

----->时间复杂度：O(n)

 

空间复杂度(数据规模之间的增长关系【对象的个数】)

1.递归

int guiMethod(int n){ if(n==1) return n; return guiMethod(n-1)}

----->空间复杂度：O(n)

2.非递归

int unGuiMethod(int n){ if(n<2) return n; return n-1;}

----->空间复杂度：O(1)

常见的时间复杂度所耗费的时间从小到大依次是：

O(1) < O(logN) < O(N) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)