手把手帶你刷力扣(1)-時(shí)間復(fù)雜度和空間復(fù)雜度
時(shí)間復(fù)雜度：算法的執(zhí)行效率、算法的執(zhí)行時(shí)間和輸入值的關(guān)系
需要關(guān)注的是算法中的for循環(huán)和while循環(huán)，如均沒(méi)有，時(shí)間復(fù)雜度為O(1)。
下面是常見(jiàn)時(shí)間復(fù)雜度的簡(jiǎn)單案例：
O(1):
def O1(num):
i = num
j = num * 2
return i + j
O(logN):
def OlogN(num):
i = 1
while (i < num):
i = i * 2
return i
O(N):
def ON(num):
total = 0
for i in range(num):
total += i
return total
O(M+N):
def OMN(num1,num2):
toal = 0;
for i in range(num1):
total += i
for j in range(num2):
total += j
return total
O(NlogN):
def ONLogN(num):
total = 0
j = 1
for i in range(num):
while(j < num):
total += i + j
j =j * 2
return total
O(N2):
def ON2(num):
total = 0
for i in range(num）：
for j in range(num）：
total += i + j
return total
對(duì)比：
O(1) < O(logN)(二分查找) < O(N) < O(NlogN) (排序)< O(N2) < O(2N) < O(N!)
空間復(fù)雜度：算法存儲(chǔ)空間與輸入值之間的關(guān)系
簡(jiǎn)單案例：
O(1):
def test1(num):
total = 0
for i in range(num):
total += i
return total
O(N):
def test2(num):
array = []
for num in nums:
array.append(num)
return array
對(duì)比：
O(1) < O(N) < O(N2)
posted on 2022-04-29 10:44 Monocy219 閱讀(152) 評(píng)論(0) 收藏 舉報(bào)
浙公網(wǎng)安備 33010602011771號(hào)