时间复杂度与空间复杂度

前言
代码的高效运行最直接的方式是简洁的代码,代码的高效运行最直接的体现是在两方面:一种是空间复杂度低,一种是时间复杂度低
何为时间复杂度
时间复杂度:在计算机当中,算法的时间复杂度是可具化的,用一个函数来进行估算一个值。现在的电脑处理器是多种多样的,同样的代码放在windows和mac上花费的时间也是不尽相同的。假设我们的代码每执行一次所耗费的时间是相同的,那么我们执行的次数越多,时间复杂度也就相对的越高。
怎样计算时间复杂度
就像我们学习定理一样,时间复杂度也有对应的公式,时间复杂度也是表示计算一段代码所执行的总次数。
T(n):表示语句频度,代码执行过程中所要执行的次数。 T :total
f(n):表示代码执行时,问题的的复杂程度 f:function
很显然a不能为0,通常我们表示复杂度的时候用O(x)来进行表示。机器运行代码的速度很快,一两行代码在几微秒就可以执行完成,这样的时间我们完全可以忽略不计。
常见的时间复杂度如下:
O(1)
一般来说,只要算法里没有特殊的递归遍历他的复杂程度都是默认为1,因为代码的执行次数不会因为变量的改变而改变执行的次数。
function f1(){
const n =1000;
console.log(n);
console.log(1111);
console.log(2222);
}
function f2(){
const n =9999;
console.log(n);
console.log(33333);
console.log(44444);
}
```
/** f1和f2都是O(1),执行的次数并不会随着n的大小而改变
```
O(n)
递归循环遍历只有一层,随着n的改变而改变
function f1(){
const n =1000;
for (let i =0;i<n;i++){
console.log(i)
}
}
function f2(){
const n =1000;
for (let i =0;i<n;i++){
console.log(i)
}
}
O(n方) 函数多层嵌套循环,每增加一层就*n
function f1(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log("操盘手该杀")
}
}
}
function f2(n){
for( let k = 0; k < n; k++){
console.log("今天周一")
}
for( let i = 0; i < n; i++){
for( let j = 0; j < n; j++){
console.log("疯狂星期四")
}
}
}
f2的计算结果是n+(n的平方),在计算多项式时我们只计算最高次项,所以计为n的平方.同理,5n+(n三次方)+1000,我们也只计为n的三次方
二分查找法log(n)
假设有一电线中间断了,那么最快查找到断线之处就是每次选择一半进行查看,如果第一次没发现就选择一半的一半进行查看,依次类推。
function f1(m) {
let stop = false;
const flag = 1;
while (m > 1) {
m = m / 2;
let stop = m.includes(1) ? true : false;
}
return stop
}
何为空间复杂度
我们知道,代码在运行时是要首先处理我们的代码转变成机器码,然后保存这些机器码进行一个计算,空间复杂度讲的就是代码在机器上所占用空间的大小。
常见的空间复杂度:O(1)| O(n) | O(n次方)
O(1)
不因变量大小而进行递归的计算,只执行固定的次数
function f1(){
const test =10;
console.log(test);
console.log(1);
console.log(2);
console.log(3)
}
O(n)
通过递归遍历,由n的大小来改变执行的次数,执行的越多,所占用的空间越大
function f1(n) {
let arr = [];
for (let i = 0; i < n; i++) {
console.log(4 * i);
arr.push(i);
}
return arr;
}
O(n次方)
函数进行了多层的嵌套遍历,嵌套越多,占用的空间也就越大
function f1(n) {
let arr = [];
for (let i = 0; i < n; i++) {
console.log(4 * i);
for (let k=0;k<2n;k++){
console.log(3*k);
}
arr.push(i);
}
return arr;
}
其实,我们在生活中更看重时间复杂度,现在的电脑最少都是几个G的运行内存,完全没必要因为这点空间而担心,我们在编写代码的时候主要是看代码的嵌套,如果一个函数是指数级的增加时间,那么你就要小心了,电脑分分钟给你罢工。