#3 & #4 Time dan Space Complexity

Time complexity
Jumlah MASA yang diambil untuk sesuatu program dijalankan

Space complexity
Jumlah RUANG/MEMORI yang digunakan untuk sesuatu program

🧮 Tips Pengiraan

Time

  1. Kira berapa baris kod yang ada
  2. Satu operasi – O(1): constant time
  3. Kalau ada loop yang tidak diketahui berapa banyak – O(n): linear time
  4. Cari terma yang paling tinggi
  5. Permudahkan

Space

  1. Mencipta variable satu data - O(1): constant space
  2. strings, arrays, object - O(n): linear space
  3. Cari terma yang paling tinggi
  4. 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)