Len mengatur kompleksitas waktu python

Saat ini, dengan semua data yang kami konsumsi dan hasilkan setiap hari, algoritme harus cukup baik untuk menangani operasi dalam volume data yang besar

Dalam posting ini, kita akan memahami lebih banyak tentang kompleksitas waktu, notasi Big-O dan mengapa kita perlu memperhatikannya saat mengembangkan algoritme

Contoh yang ditampilkan dalam cerita ini dikembangkan dengan Python, jadi akan lebih mudah dipahami jika Anda memiliki setidaknya pengetahuan dasar tentang Python, tetapi ini bukan prasyarat.

Mari kita mulai memahami apa itu kompleksitas komputasi

Kompleksitas komputasi adalah bidang dari ilmu komputer yang menganalisis algoritma berdasarkan jumlah sumber daya yang diperlukan untuk menjalankannya. Jumlah sumber daya yang dibutuhkan bervariasi berdasarkan ukuran masukan, sehingga kompleksitas umumnya dinyatakan sebagai fungsi dari n, dimana n adalah ukuran masukan

Penting untuk dicatat bahwa ketika menganalisis suatu algoritma, kita dapat mempertimbangkan kompleksitas waktu dan kompleksitas ruang. Kompleksitas ruang pada dasarnya adalah jumlah ruang memori yang diperlukan untuk menyelesaikan masalah terkait dengan ukuran input. Meskipun kompleksitas ruang penting saat menganalisis suatu algoritme, dalam cerita ini kita hanya akan fokus pada kompleksitas waktu

Saat Anda membaca cerita ini sekarang, Anda mungkin memiliki gagasan tentang apa itu kompleksitas waktu, tetapi untuk memastikan kita semua berada di halaman yang sama, mari kita mulai memahami apa arti kompleksitas waktu dengan deskripsi singkat dari Wikipedia

Dalam ilmu komputer, kompleksitas waktu adalah kompleksitas komputasi yang menjelaskan jumlah waktu yang dibutuhkan untuk menjalankan suatu algoritma. Kompleksitas waktu biasanya diperkirakan dengan menghitung jumlah operasi elementer yang dilakukan oleh algoritma, dengan anggapan bahwa setiap operasi elementer membutuhkan waktu yang tetap untuk dilakukan.

Ketika menganalisis kompleksitas waktu dari suatu algoritma, kita dapat menemukan tiga kasus. kasus terbaik, kasus rata-rata, dan kasus terburuk. Mari kita pahami apa artinya

Misalkan kita memiliki daftar yang tidak disortir berikut [1, 5, 3, 9, 2, 4, 6, 7, 8] dan kita perlu menemukan indeks nilai dalam daftar ini menggunakan pencarian linier

• kasus terbaik. ini adalah kompleksitas pemecahan masalah untuk input terbaik. Dalam contoh kami, kasus terbaik adalah mencari nilai 1. Karena ini adalah nilai pertama dari daftar, ini akan ditemukan pada iterasi pertama
• kasus rata-rata. ini adalah kompleksitas rata-rata penyelesaian masalah. Kompleksitas ini didefinisikan sehubungan dengan distribusi nilai dalam data masukan. Mungkin ini bukan contoh terbaik tetapi, berdasarkan sampel kami, kami dapat mengatakan bahwa kasus rata-rata adalah ketika kami mencari beberapa nilai di "tengah" daftar, misalnya, nilai 2
• kasus terburuk. ini adalah kompleksitas pemecahan masalah untuk input ukuran n terburuk. Dalam contoh kita, kasus terburuk adalah mencari nilai 8, yang merupakan elemen terakhir dari daftar

Biasanya, saat menjelaskan kompleksitas waktu suatu algoritme, kita berbicara tentang kasus terburuk

Ok, tapi bagaimana kita menjelaskan kompleksitas waktu dari sebuah algoritma?

Kami menggunakan notasi matematika yang disebut Big-O

Notasi Big-O, kadang-kadang disebut "notasi asimtotik", adalah notasi matematika yang menggambarkan perilaku pembatas suatu fungsi ketika argumen cenderung ke arah nilai atau tak terhingga tertentu

Dalam ilmu komputer, notasi Big-O digunakan untuk mengklasifikasikan algoritme menurut bagaimana kebutuhan waktu atau ruang berjalannya bertambah seiring dengan bertambahnya ukuran input (n). Notasi ini mencirikan fungsi sesuai dengan tingkat pertumbuhannya. fungsi yang berbeda dengan laju pertumbuhan yang sama dapat direpresentasikan menggunakan notasi O yang sama

Mari kita lihat beberapa kompleksitas waktu umum yang dijelaskan dalam notasi Big-O

Tabel kompleksitas waktu umum

Ini adalah kompleksitas waktu paling umum yang diekspresikan menggunakan notasi Big-O

╔══════════════════╦═════════════════╗
║       Name       ║ Time Complexity ║
╠══════════════════╬═════════════════╣
║ Constant Time    ║       O(1)      ║
╠══════════════════╬═════════════════╣
║ Logarithmic Time ║     O(log n)    ║
╠══════════════════╬═════════════════╣
║ Linear Time      ║       O(n)      ║
╠══════════════════╬═════════════════╣
║ Quasilinear Time ║    O(n log n)   ║
╠══════════════════╬═════════════════╣
║ Quadratic Time   ║      O(n^2)     ║
╠══════════════════╬═════════════════╣
║ Exponential Time ║      O(2^n)     ║
╠══════════════════╬═════════════════╣
║ Factorial Time   ║       O(n!)     ║
╚══════════════════╩═════════════════╝

Perhatikan bahwa kami akan memfokuskan studi kami dalam kompleksitas waktu yang umum ini, tetapi ada beberapa kompleksitas waktu lain di luar sana yang dapat Anda pelajari nanti.

Seperti yang sudah dikatakan, kami biasanya menggunakan notasi Big-O untuk menggambarkan kompleksitas waktu dari algoritma. Ada banyak matematika yang terlibat dalam definisi formal notasi, tetapi secara informal kita dapat berasumsi bahwa notasi Big-O memberi kita perkiraan waktu berjalan algoritme dalam kasus terburuk. Saat menggunakan notasi Big-O, kami menggambarkan efisiensi algoritme berdasarkan peningkatan ukuran data input (n). Misalnya, jika inputnya adalah string, n akan menjadi panjang string. Jika ini adalah daftar, n akan menjadi panjang daftar dan seterusnya

Sekarang, mari kita telusuri setiap kompleksitas waktu umum ini dan lihat beberapa contoh algoritme. Perhatikan bahwa saya mencoba mengikuti pendekatan berikut. sajikan sedikit deskripsi, tunjukkan contoh sederhana dan mudah dipahami dan tunjukkan contoh yang lebih kompleks (biasanya dari masalah dunia nyata)

Waktu Konstan — O(1)

Suatu algoritma dikatakan memiliki waktu yang konstan ketika tidak bergantung pada input data (n). Berapapun ukuran input datanya, running time akan selalu sama. Sebagai contoh

if a > b:
    return True
else:
    return False

Sekarang, mari kita lihat fungsi get_first yang mengembalikan elemen pertama dari sebuah list

def get_first(data):
    return data[0]
    
if __name__ == '__main__':
    data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
    print(get_first(data))

Terlepas dari ukuran data input, itu akan selalu memiliki waktu berjalan yang sama karena hanya mendapatkan nilai pertama dari daftar

Algoritme dengan kompleksitas waktu yang konstan sangat baik karena kita tidak perlu mengkhawatirkan ukuran masukan

Waktu Logaritmik — O(log n)

Algoritma dikatakan memiliki kompleksitas waktu logaritmik ketika ia mengurangi ukuran data input di setiap langkah (tidak perlu melihat semua nilai data input), misalnya

for index in range(0, len(data), 3):
    print(data[index])

Algoritma dengan kompleksitas waktu logaritmik umumnya ditemukan dalam operasi pada pohon biner atau saat menggunakan pencarian biner. Mari kita lihat contoh pencarian biner, di mana kita perlu menemukan posisi suatu elemen dalam daftar yang diurutkan

def binary_search(data, value):
    n = len(data)
    left = 0
    right = n - 1
    while left <= right:
        middle = (left + right) // 2
        if value < data[middle]:
            right = middle - 1
        elif value > data[middle]:
            left = middle + 1
        else:
            return middle
    raise ValueError('Value is not in the list')
    
if __name__ == '__main__':
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    print(binary_search(data, 8))

Langkah-langkah pencarian biner

• Hitung bagian tengah daftar
• Jika nilai yang dicari lebih rendah dari nilai di tengah daftar, atur batas kanan yang baru
• Jika nilai yang dicari lebih tinggi dari nilai di tengah daftar, atur batas kiri yang baru
• Jika nilai pencarian sama dengan nilai di tengah daftar, kembalikan tengah (indeks)
• Ulangi langkah di atas hingga nilai ditemukan atau batas kiri sama atau lebih tinggi dari batas kanan

Penting untuk dipahami bahwa algoritme yang harus mengakses semua elemen data inputnya tidak dapat mengambil waktu logaritmik, karena waktu yang dibutuhkan untuk membaca input ukuran n adalah urutan n

Waktu Linier — O(n)

Suatu algoritma dikatakan memiliki kompleksitas waktu linier ketika waktu berjalan meningkat paling banyak secara linier dengan ukuran data masukan. Ini adalah kompleksitas waktu terbaik ketika algoritme harus memeriksa semua nilai dalam data input. Sebagai contoh

for value in data:
    print(value)

Mari kita lihat contoh pencarian linier, di mana kita perlu menemukan posisi elemen dalam daftar yang tidak disortir

def linear_search(data, value):
    for index in range(len(data)):
        if value == data[index]:
            return index
    raise ValueError('Value not found in the list')
    
if __name__ == '__main__':
    data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
    print(linear_search(data, 7))

Perhatikan bahwa dalam contoh ini, kita perlu melihat semua nilai dalam daftar untuk menemukan nilai yang kita cari

Waktu Quasilinear — O(n log n)

Suatu algoritma dikatakan memiliki kompleksitas waktu quasilinear ketika setiap operasi dalam input data memiliki kompleksitas waktu logaritma. Ini biasanya terlihat dalam algoritma pengurutan (mis. g. mergesort, timsort, heapsort)

Sebagai contoh. untuk setiap nilai di data1 (O(n)) gunakan pencarian biner (O(log n)) untuk mencari nilai yang sama di data2

for value in data1:
    result.append(binary_search(data2, value))

Contoh lain yang lebih kompleks dapat ditemukan dalam algoritma Mergesort. Mergesort adalah algoritma pengurutan berbasis perbandingan yang efisien, bertujuan umum, dan memiliki kompleksitas waktu quasilinear, mari kita lihat contohnya

def merge_sort(data):
    if len(data) <= 1:
        return
    
    mid = len(data) // 2
    left_data = data[:mid]
    right_data = data[mid:]
    
    merge_sort(left_data)
    merge_sort(right_data)
    
    left_index = 0
    right_index = 0
    data_index = 0
    
    while left_index < len(left_data) and right_index < len(right_data):
        if left_data[left_index] < right_data[right_index]:
            data[data_index] = left_data[left_index]
            left_index += 1
        else:
            data[data_index] = right_data[right_index]
            right_index += 1
        data_index += 1
    
    if left_index < len(left_data):
        del data[data_index:]
        data += left_data[left_index:]
    elif right_index < len(right_data):
        del data[data_index:]
        data += right_data[right_index:]
    
if __name__ == '__main__':
    data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
    merge_sort(data)
    print(data)

Gambar berikut mencontohkan langkah-langkah yang diambil oleh algoritma mergesort

Perhatikan bahwa dalam contoh ini penyortiran dilakukan di tempat

Waktu Kuadrat — O(n²)

Algoritma dikatakan memiliki kompleksitas waktu kuadrat ketika perlu melakukan operasi waktu linier untuk setiap nilai dalam data input, misalnya

for x in data:
    for y in data:
        print(x, y)

Bubble sort adalah contoh bagus kompleksitas waktu kuadrat karena untuk setiap nilai perlu dibandingkan dengan semua nilai lain dalam daftar, mari kita lihat contohnya

if a > b:
    return True
else:
    return False

Waktu Eksponensial — O(2^n)

Algoritme dikatakan memiliki kompleksitas waktu eksponensial ketika pertumbuhan berlipat ganda dengan setiap penambahan set data input. Kompleksitas waktu seperti ini biasanya terlihat pada algoritma brute-force

Seperti yang dicontohkan oleh Vicky Lai

Dalam kriptografi, serangan brute-force dapat secara sistematis memeriksa semua kemungkinan elemen kata sandi dengan mengulang melalui himpunan bagian. Menggunakan algoritme eksponensial untuk melakukan ini, menjadi sangat mahal sumber daya untuk memaksa secara kasar memecahkan kata sandi yang panjang versus kata sandi yang lebih pendek. Inilah salah satu alasan mengapa kata sandi yang panjang dianggap lebih aman daripada kata sandi yang lebih pendek

Contoh lain dari algoritma waktu eksponensial adalah perhitungan rekursif angka Fibonacci

if a > b:
    return True
else:
    return False

Jika Anda tidak tahu apa itu fungsi rekursif, mari kita perjelas dengan cepat. fungsi rekursif dapat digambarkan sebagai fungsi yang memanggil dirinya sendiri dalam kondisi tertentu. Seperti yang mungkin telah Anda ketahui, kompleksitas waktu dari fungsi rekursif sedikit lebih sulit untuk ditentukan karena bergantung pada berapa kali fungsi dipanggil dan kompleksitas waktu dari pemanggilan fungsi tunggal.

Lebih masuk akal ketika kita melihat pohon rekursi. Pohon rekursi berikut dihasilkan oleh algoritma Fibonacci menggunakan n = 4

Perhatikan bahwa ia akan memanggil dirinya sendiri hingga mencapai daun. Saat mencapai daun, ia mengembalikan nilai itu sendiri

Sekarang, lihat bagaimana pohon rekursi tumbuh hanya dengan menambah n menjadi 6

Anda dapat menemukan penjelasan yang lebih lengkap tentang kompleksitas waktu dari algoritme Fibonacci rekursif di sini di StackOverflow

Faktorial — O(n. )

Algoritma dikatakan memiliki kompleksitas waktu faktorial ketika tumbuh secara faktorial berdasarkan ukuran data input, misalnya

if a > b:
    return True
else:
    return False

Seperti yang Anda lihat, pertumbuhannya sangat cepat, bahkan untuk masukan ukuran kecil

Contoh bagus dari algoritme yang memiliki kompleksitas waktu faktorial adalah algoritme Heap, yang digunakan untuk menghasilkan semua kemungkinan permutasi dari n objek

Menurut Wikipedia

Heap menemukan metode sistematis untuk memilih pada setiap langkah sepasang elemen untuk ditukar, untuk menghasilkan setiap permutasi yang mungkin dari elemen-elemen ini tepat satu kali.

Mari kita lihat contohnya

if a > b:
    return True
else:
    return False

Hasilnya akan

if a > b:
    return True
else:
    return False

Perhatikan bahwa ini akan tumbuh dengan cara faktorial, berdasarkan ukuran data input, jadi kita dapat mengatakan bahwa algoritme memiliki kompleksitas waktu faktorial O(n. )

Contoh bagus lainnya adalah Travelling Salesman Problem

Penting untuk dicatat bahwa ketika menganalisis kompleksitas waktu dari suatu algoritma dengan beberapa operasi, kita perlu menggambarkan algoritma berdasarkan kompleksitas terbesar di antara semua operasi. Sebagai contoh

if a > b:
    return True
else:
    return False

Bahkan operasi di 'my_function' tidak masuk akal, kita dapat melihat bahwa itu memiliki banyak kompleksitas waktu. O(1) + O(n) + O(n²). Jadi, saat memperbesar ukuran data input, hambatan dari algoritme ini adalah operasi yang membutuhkan O(n²). Berdasarkan ini, kita dapat menggambarkan kompleksitas waktu dari algoritma ini sebagai O(n²)

Untuk membuat hidup Anda lebih mudah, di sini Anda dapat menemukan lembar dengan kompleksitas waktu operasi dalam struktur data yang paling umum

Ini adalah lembar lain dengan kompleksitas waktu dari algoritma pengurutan yang paling umum

Jika setelah membaca semua cerita ini Anda masih ragu tentang pentingnya mengetahui kompleksitas waktu dan notasi Big-O, mari kita perjelas beberapa poin

Bahkan saat bekerja dengan bahasa modern, seperti Python, yang menyediakan fungsi bawaan, seperti algoritme pengurutan, suatu hari nanti Anda mungkin perlu mengimplementasikan algoritme untuk melakukan beberapa jenis operasi dalam jumlah data tertentu. Dengan mempelajari kompleksitas waktu, Anda akan memahami konsep efisiensi yang penting dan akan dapat menemukan kemacetan dalam kode Anda yang harus diperbaiki, terutama saat bekerja dengan kumpulan data yang sangat besar

Selain itu, jika Anda berencana untuk melamar posisi insinyur perangkat lunak di perusahaan besar seperti Google, Facebook, Twitter, dan Amazon, Anda harus siap menjawab pertanyaan tentang kompleksitas waktu menggunakan notasi Big-O.

Terima kasih telah membaca cerita ini. Saya harap Anda telah belajar lebih banyak tentang kompleksitas waktu dan notasi Big-O. Jika Anda menikmatinya, tolong beri tepuk tangan dan bagikan. Jika Anda memiliki keraguan atau saran, jangan ragu untuk berkomentar atau mengirim saya email. Juga, silakan ikuti saya di Twitter, Linkedin, dan Github

Apa kompleksitas waktu set Python?

Apakah Len () dari daftar 1 Python?

Apa itu set Len ()) dengan Python?

Bisakah LEN digunakan pada set?