时间复杂度-空间复杂度

时间复杂度

时间复杂度：时间增长趋势 T(n) = O(f(n))

for(let i=0;i<=n;i++){
	x++
}
// let i=0   1
// i<=n; i++; x++ 各n次
// 结果为 O(1+3n) = O(n)   O(n)算n趋近无限大，所以常数忽略

for(let i=0;i<=n;i++){
	for(let j=0;j<=n;j++){
		x++
	}
}
// 时间复杂度：O(n)*O(n)=O(n^2)

for(let i=0;i<=n;i++){
	x++
}
for(let i=0;i<=n;i++){
	for(let j=0;j<=n;j++){
		x++
	}
}
// 时间复杂度 O(n+n^2) = O(n^2)

let x = 0
let y = 1
let temp = x
x = y
y = temp
// 时间复杂度不随着任何一个变量增大而增大，复杂度为O(1)


let i = 1
while(i<n){
    i = i*2
}
// 循环次数k：2^k = n k=logn O(logn)


for(let j=0;j<=n;j++){
	let i = 1
    while(i<n){
        i = i*2
    }
}
// 时间复杂度O(n)*O(logn) = O(nlogn)


for(let i=0;i<=n;i++){
	for(let j=0;j<=m;j++){
		x++
	}
}
// 时间复杂度O(n)*O(m) = O(nm)

空间复杂度

空间复杂度：内存空间增长的趋势

let x = 0
let y = 1
let temp = x
x = y
y = temp
// x和y无论多大多不会影响空间占用 O(1)
let arr = []
for(let i=0;i<n;i++){
	arr.push(i)
} 
// 占用空间与n成正比，O(n)