复杂度

什么是复杂度？

• 程序执行时需要的计算量和内存空间（和代码是否简洁无关）
• 复杂度是数量级（表示一个范围），不是具体数量
• 一般针对于一个具体的算法，而非整个系统

使用函数表示复杂度

时间复杂度

• 程序执行时需要的计算量（CPU） ```typescript // O(1) 输入什么便是什么 function fnO1(obj = {}, key){ return obj[key] }

// O(logn) function fnOlogn(n) { let num = 1; // 语句执行一次 while (num < n) { // 语句执行logn次 // 这里的2是log的底数 // 底数在大O符号中是省去的 num *= 2; // 语句执行logn次 } }

// O(n) 输入量等于计算量 function fnOn(arr) { for(let i = 0;i < arr.length; i++) { console.log(arr[i]) } }

// O(nlogn)

// O(n^2) 计算量是输入量的n^2被 function fnOn2(arr) { for(let i = 0;i < arr.length; i++) { console.log(arr[i]) for(let j = 0;j < arr.length; j++ ) { console.log(arr[j]); } } } ```

空间复杂度

• 程序执行时需要的内存空间