Time complexity
Jumlah MASA yang diambil untuk sesuatu program dijalankan
Space complexity
Jumlah RUANG/MEMORI yang digunakan untuk sesuatu program
🧮 Tips Pengiraan
Time
- Kira berapa baris kod yang ada
- Satu operasi – O(1): constant time
- Kalau ada loop yang tidak diketahui berapa banyak – O(n): linear time
- Cari terma yang paling tinggi
- Permudahkan
Space
- Mencipta variable satu data - O(1): constant space
- strings, arrays, object - O(n): linear space
- Cari terma yang paling tinggi
- Permudahkan
🤔 Contoh Pengiraan
def add(x, y):
answer = x + y # 1
return answer # 1
# Time
# f(n) = 2
# O(1)
# Space
# x , y , answer
# f(n) = 3
# O(1)
def mult2(arr):
result = [] # 1
for x in arr: # n * 2
multBy2 = x * 2 # 1
result.append(multBy2) # 1
return result # 1
# Time
# f(n) = 2n + 2
# O(n)
# Space
# result(n), arr(n), x, multBy2
# f(n) = 2n + 2
# O(n)
def randomFunc(arr):
x = 1 + 1 # 1
y = 3 + x # 1
for z in arr: # n * 2
print(y) # 1
print(x) # 1
for x in arr: # n * n * 1
for y in arr: # n * 1
print("Hello") # 1
# Time
# f(n) = 2 + 2n + n^2
# O(n^2)
# Space
# x , y, arr(n), z
# f(n) = n + 3
# O(n)
👨💻 Latihan
Fungsi lain yang tidak ditunjukkan di video yang boleh anda cuba
def average3(x, y, z):
sum = x + y + z # 1
average = sum / 3 # 1
return average # 1
# Time
# f(n) = 3
# O(1)
# Space
# x , y , z , sum , average
# f(n) = 5
# O(1)
def swap(a, b):
temp = a # 1
a = b # 1
b = temp # 1
print (a, b) # 1
# Time
# f(n) = 4
# O(1)
# Space
# a, b, temp
# f(n) = 3
# O(1)
def doIt10(str1):
for x in range(10): # 10 * 2
print(str1) # 1
print(str1) # 1
# Time
# f(n) = 20
# O(1)
# Space
# x , str1 , range(10)=10
# f(n) = 12
# O(1)
❗ Nota
kalau time ⬇️, space ⬆️
kalau space⬇️, time ⬆️
lebih pentingkan time sebab masa itu emas, space kita boleh beli lagi (RAM lagi besar)