Python MIT 6.100L: Kompleksitas Algoritma, Big-O, Sorting, Visualisasi

1
import time
2

3
def jumlah_kuadrat(n):
4
    total = 0
5
    for i in range(n):
6
        total += i ** 2
7
    return total
8

9
mulai = time.time()
10
jumlah_kuadrat(100000)
11
selesai = time.time()
12
print(f"Waktu: {selesai - mulai:.4f} detik")

1
def cari_maks(L):
2
    maks = L[0]          # 1 operasi
3
    for x in L:          # n iterasi
4
        if x > maks:     # 1 perbandingan per iterasi = n operasi
5
            maks = x     # paling banyak n assignment
6
    return maks          # 1 operasi
7

8
# Total: 1 + n + n + n + 1 = 3n + 2 operasi
9
# Untuk n = 1000: 3002 operasi
10
# Untuk n = 10000: 30002 operasi
11
# → tumbuh LINEAR terhadap n

1
def cek_duplikat(L):
2
    for i in range(len(L)):          # n iterasi luar
3
        for j in range(i + 1, len(L)):  # ~n iterasi dalam
4
            if L[i] == L[j]:
5
                return True
6
    return False
7

8
# Total: ~n²/2 operasi
9
# Untuk n = 1000: ~500.000 operasi
10
# Untuk n = 10000: ~50.000.000 operasi
11
# → tumbuh KUADRATIK terhadap n

1
3n + 2          → O(n)       abaikan konstanta, ambil term dominan
2
n² + 100n + 50  → O(n²)      n² tumbuh jauh lebih cepat dari 100n
3
2^n + n¹⁰⁰     → O(2^n)     eksponensial mendominasi polinomial apapun

1
# Cara menentukan Big-O dari kode
2

3
# O(1) — tidak bergantung pada input
4
def ambil_pertama(L):
5
    return L[0]
6

7
# O(n) — satu loop linear
8
def hitung_total(L):
9
    return sum(L)
10

11
# O(n²) — nested loop
12
def semua_pasangan(L):
13
    for i in L:
14
        for j in L:
15
            print(i, j)
16

17
# O(log n) — input dibagi dua tiap iterasi
18
def bisection(n):
19
    low, high = 0, n
20
    while low < high:
21
        mid = (low + high) // 2
22
        # ...
23
        high = mid  # atau low = mid + 1
24

25
# O(n log n) — loop + bisection di dalamnya
26
# O(2^n) — rekursi dengan dua cabang
27
def fib(n):
28
    if n <= 1: return n
29
    return fib(n-1) + fib(n-2)  # dua panggilan rekursif = O(2^n)

1
T(n) = Θ(f(n)) berarti:
2
  - T(n) = O(f(n))  → tidak tumbuh lebih cepat dari f(n)
3
  - T(n) = Ω(f(n))  → tidak tumbuh lebih lambat dari f(n)

1
import math
2

3
# Visualisasi pertumbuhan untuk n = 20
4
n = 20
5
print(f"O(1)      : 1")
6
print(f"O(log n)  : {math.log2(n):.1f}")
7
print(f"O(n)      : {n}")
8
print(f"O(n log n): {n * math.log2(n):.1f}")
9
print(f"O(n²)     : {n**2}")
10
print(f"O(2^n)    : {2**n}")
11
print(f"O(n!)     : {math.factorial(n):.2e}")

1
def linear_search(L, target):
2
    for item in L:          # worst case: n iterasi
3
        if item == target:
4
            return True
5
    return False
6

7
# Best case:  O(1) — target di index 0
8
# Worst case: O(n) — target tidak ada atau di akhir
9
# Average:    O(n/2) = O(n)

1
def binary_search(L, target):
2
    low, high = 0, len(L) - 1
3
    while low <= high:
4
        mid = (low + high) // 2
5
        if L[mid] == target:
6
            return mid
7
        elif L[mid] < target:
8
            low = mid + 1   # buang setengah kiri
9
        else:
10
            high = mid - 1  # buang setengah kanan
11
    return -1
12

13
# Setiap iterasi membuang SETENGAH kemungkinan
14
# n → n/2 → n/4 → ... → 1 : butuh log₂(n) langkah
15
# Untuk n = 1.000.000: hanya ~20 langkah!

1
import random
2

3
def bogo_sort(L):
4
    """Acak terus sampai terurut — algoritma terburuk."""
5
    while L != sorted(L):
6
        random.shuffle(L)
7
    return L
8
# Complexity: rata-rata O(n × n!) — praktis tidak berguna

1
def bubble_sort(L):
2
    n = len(L)
3
    for i in range(n):
4
        for j in range(0, n - i - 1):
5
            if L[j] > L[j + 1]:
6
                L[j], L[j + 1] = L[j + 1], L[j]  # swap
7
    return L
8

9
# Cara kerja: elemen besar "menggelembung" ke akhir
10
# [5, 3, 1, 4] → [3, 1, 4, 5] → [1, 3, 4, 5]
11
# O(n²) — dua nested loop

1
def selection_sort(L):
2
    for i in range(len(L)):
3
        min_idx = i
4
        for j in range(i + 1, len(L)):
5
            if L[j] < L[min_idx]:
6
                min_idx = j
7
        L[i], L[min_idx] = L[min_idx], L[i]  # taruh minimum di posisi i
8
    return L

1
def merge_sort(L):
2
    if len(L) <= 1:
3
        return L
4

5
    # Bagi dua
6
    mid = len(L) // 2
7
    kiri = merge_sort(L[:mid])   # sort kiri secara rekursif
8
    kanan = merge_sort(L[mid:])  # sort kanan secara rekursif
9

10
    # Gabungkan (merge) dua list yang sudah terurut
11
    return merge(kiri, kanan)
12

13
def merge(kiri, kanan):
14
    hasil = []
15
    i = j = 0
16
    while i < len(kiri) and j < len(kanan):
17
        if kiri[i] <= kanan[j]:
18
            hasil.append(kiri[i])
19
            i += 1
20
        else:
21
            hasil.append(kanan[j])
22
            j += 1
23
    hasil.extend(kiri[i:])
24
    hasil.extend(kanan[j:])
25
    return hasil
26

27
# Kompleksitas: O(n log n) — n untuk merge, log n untuk rekursi
28
# [5,3,1,4,2] → [5,3] [1,4,2] → [5][3] [1][4,2] → ... merge

1
angka = [5, 2, 8, 1, 9, 3]
2
terurut = sorted(angka)        # buat list baru
3
angka.sort()                   # sort in-place
4
angka.sort(reverse=True)       # descending

1
# Mengapa ini O(1)?
2
d = {"nama": "Rifky", "umur": 25}
3
print(d["nama"])  # langsung, tidak perlu scan satu per satu

1
print(hash("nama"))   # misalnya: -4384838292
2
print(hash("umur"))   # misalnya: 8732919123
3
print(hash(42))       # 42 (integer hash ke dirinya sendiri)
4

5
# Demonstrasi mengapa list tidak bisa jadi key dict
6
d[["a", "b"]] = 1  # TypeError: unhashable type: 'list'
7
# List mutable → hash bisa berubah → tidak bisa jadi key
8
# Tuple boleh karena immutable
9
d[("a", "b")] = 1  # ✓

1
import matplotlib.pyplot as plt
2
import numpy as np
3

4
# Plot sederhana
5
x = list(range(0, 11))
6
y = [xi ** 2 for xi in x]
7

8
plt.figure(figsize=(8, 5))
9
plt.plot(x, y, 'b-o', label='y = x²')
10
plt.title('Grafik Kuadrat')
11
plt.xlabel('x')
12
plt.ylabel('y')
13
plt.legend()
14
plt.grid(True)
15
plt.savefig('kuadrat.png', dpi=150)
16
plt.show()

1
import matplotlib.pyplot as plt
2
import numpy as np
3

4
n = np.linspace(1, 20, 100)
5

6
plt.figure(figsize=(10, 6))
7
plt.plot(n, np.ones_like(n),     label='O(1)',      linewidth=2)
8
plt.plot(n, np.log2(n),          label='O(log n)',  linewidth=2)
9
plt.plot(n, n,                   label='O(n)',       linewidth=2)
10
plt.plot(n, n * np.log2(n),      label='O(n log n)',linewidth=2)
11
plt.plot(n, n ** 2,              label='O(n²)',      linewidth=2)
12
plt.plot(n, 2 ** n,              label='O(2^n)',     linewidth=2)
13

14
plt.ylim(0, 200)
15
plt.xlabel('Ukuran Input (n)')
16
plt.ylabel('Jumlah Operasi')
17
plt.title('Perbandingan Kelas Kompleksitas')
18
plt.legend()
19
plt.grid(True, alpha=0.3)
20
plt.savefig('kompleksitas.png', dpi=150)
21
plt.show()

1
# Bar chart
2
kategori = ['O(log n)', 'O(n)', 'O(n log n)', 'O(n²)']
3
nilai_n1000 = [10, 1000, 10000, 1000000]
4

5
plt.figure(figsize=(8, 5))
6
plt.bar(kategori, nilai_n1000, color=['green', 'blue', 'orange', 'red'])
7
plt.yscale('log')  # skala logaritmik untuk range besar
8
plt.title('Operasi untuk n = 1000')
9
plt.ylabel('Jumlah Operasi (skala log)')
10
plt.savefig('bar_kompleksitas.png')
11
plt.show()
12

13
# Histogram dari data random
14
data = np.random.normal(loc=50, scale=10, size=1000)
15
plt.figure(figsize=(8, 5))
16
plt.hist(data, bins=30, edgecolor='black', color='steelblue', alpha=0.7)
17
plt.title('Distribusi Normal')
18
plt.xlabel('Nilai')
19
plt.ylabel('Frekuensi')
20
plt.savefig('histogram.png')
21
plt.show()