Python dalam kompleksitas waktu fungsi

Question

Kompleksitas Waktu memberi tahu kita tentang berapa lama suatu algoritme dijalankan, relatif terhadap ukuran inputnya. Ini adalah cara cepat untuk memahami kinerja relatif dari suatu algoritma

Table of Contents Show

1. Apa itu Kompleksitas Waktu
2. Apa itu BigO?
3. O(1) Waktu Konstan
4. O(logn) Waktu Logaritmik
5. O(n) Waktu Linier
6. O(n^2) Waktu Polinomial
7. O(2^n) Waktu Eksponensial
Bagaimana Anda menemukan kompleksitas waktu suatu fungsi di Python?
Berapa kompleksitas waktu dari fungsi set di Python?
Apa kompleksitas waktu dari suatu fungsi?
Berapa kompleksitas waktu str () dengan Python?

Grafik di bawah ini memberi kita gambaran singkat tentang kerumitan waktu yang akan kita bahas dalam artikel ini

Daftar Isi

Pada artikel ini, saya akan berbicara tentang Kompleksitas Waktu, apa itu BigO, dan bagaimana BigO membantu kami meningkatkan algoritme kami

Jadi mari kita mulai dengan apa itu Kompleksitas Waktu

1. Apa itu Kompleksitas Waktu

Kompleksitas Waktu adalah berapa banyak waktu yang dibutuhkan algoritma untuk mengeksekusi. Tapi kami tidak akan menghitung waktu yang tepat untuk eksekusi algoritma. Alih-alih itu, kita akan menghitung seberapa besar pengaruh ukuran input terhadap waktu eksekusi algoritme kita

2. Apa itu BigO?

"Notasi BigO adalah notasi matematika yang menggambarkan perilaku pembatas suatu fungsi ketika argumen cenderung ke arah nilai tertentu atau tak terhingga. " -Wikipedia

Misalnya, kami memiliki O(1)_ yang merupakan singkatan dari Waktu Konstan, yang berarti bahwa waktu eksekusi algoritme kami tidak berubah dengan ukuran input

Sekarang kita telah melihat apa yang dimaksud dengan Kompleksitas Waktu dan BigO, mari kita lihat notasi BigO seperti apa yang kita miliki dan apa artinya

3. O(1) Waktu Konstan

Algoritme yang kompleksitas waktunya tidak berubah dengan ukuran input. Sesederhana itu

Misalnya, mendapatkan elemen pertama dari daftar. Ukuran input tidak memengaruhi algoritme ini, karena elemen pertama selalu yang pertama tidak peduli berapa banyak ukuran inputnya

def get_first(data):
    return data[0]
    
data = [1, 2, 3, 4]
get_first(data)

4. O(logn) Waktu Logaritmik

Berikut adalah referensi cepat untuk "Apa itu Logaritma". https. //byjus. com/matematika/logaritma/. Algoritme logaritmik membagi daftar atau struktur data lainnya menjadi bagian yang lebih kecil setiap kali dijalankan

Contoh terbaik dari algoritme yang memiliki Kompleksitas Waktu O(logn) adalah "Pencarian Biner". Pencarian biner harus dilakukan pada daftar yang diurutkan

Mari kita lihat implementasinya

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

_

Izinkan saya menjelaskan tentang algoritme ini dalam bahasa Inggris

Pergi ke tengah daftar
Periksa untuk melihat apakah elemen itu yang kita cari
Jika tidak maka periksa apakah elemen yang kita cari lebih besar dari elemen tengah
Jika ya, abaikan sisi kanan daftar ini setelah sekarang, jika tidak, abaikan sisi kiri daftar ini setelah sekarang
Dengan daftar yang tersisa, ulangi langkah 1 sampai 4

Dibandingkan dengan Pencarian Linier (Berurutan).

5. O(n) Waktu Linier

Dalam algoritma waktu linier, setiap elemen dalam input dikunjungi sekali. Saat ukuran masukan bertambah, waktu berjalan algoritme kami bertambah persis dengan ukuran masukan

Pencarian linier adalah contoh algoritma kompleksitas linier

Berikut implementasinya

#Define the linear search function
def search(lst, x):
    
    for i in range(len(lst)):
 
        if lst[i] == x:
            return i
 
    return -1

#Let's give it a try
lst = ["a","b","c","find me","d"]

print(search(lst, "find me"))

>>3

6. O(n^2) Waktu Polinomial

Algoritme yang dapat mengunjungi setiap elemen satu kali adalah algoritme linier, O(n). Biasanya ini dilakukan dengan loop yang berulang pada setiap elemen daftar

Tetapi bagaimana jika Anda memiliki loop bersarang, seperti dalam contoh ini?

lst = [1, 3, 5]
for x in lst:
    for y in lst:
        pass

Jika ini adalah O(n) algoritma, kami akan melakukan total 3 iterasi, karena daftar memiliki 3 elemen. Tetapi dengan loop bersarang, kami akhirnya melakukan 9 iterasi. Inilah mengapa kompleksitas waktu bersifat polinomial,

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

0, karena

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

1

Bubble Sort adalah contoh yang sangat bagus untuk ini

def bubbleSort(lst):
    n = len(lst)
    
    # Traverse through all list elements
    for i in range(n):
    
        # Last i elements are already in place
        for j in range(0, n-i-1):
    
            # traverse the list from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if lst[j] > lst[j+1] :
                lst[j], lst[j+1] = lst[j+1], lst[j]

# Driver code to test above
lst = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(lst)

_

Algoritme bubble sort mengambil angka pertama dan menukarnya dengan angka yang berdekatan jika urutannya salah. Ini dilakukan untuk setiap angka sampai semua angka berada dalam urutan yang benar - dan dengan demikian diurutkan

7. O(2^n) Waktu Eksponensial

Ini benar-benar yang terburuk karena paling lambat

Waktu eksponensial adalah

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

2, sehingga runtime tumbuh secara eksponensial dengan ukuran input

Katakanlah kita memiliki kata sandi yang hanya terdiri dari angka (jadi itu 10 angka, 0 hingga 9). kami ingin memecahkan kata sandi yang memiliki panjang n, jadi untuk memaksa melalui setiap kombinasi kami akan memiliki

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

3

Sebagai contoh, katakanlah kita ingin membuat kata sandi yang panjangnya 15 karakter. Jumlah semua kombinasi akan sama dengan

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

4

Contoh algoritma waktu eksponensial adalah perhitungan rekursif angka Fibonacci

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

Jadi, jelas kita tidak ingin menggunakan algoritme yang memiliki

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

5 bukan?

Katakanlah kita harus menghitung

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

6. Kita perlu melakukan ini

10 * 10 * 10 * 10 = 10^2 * 10^2

Seperti yang Anda lihat, kita harus menghitung

# Iterative Binary Search Function
# It returns the index of x in the given list if present,
# else returns -1
def binary_search(lst, x):
    low = 0
    high = len(lst) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore the left half
        if lst[mid] < x:
            low = mid + 1

            # If x is smaller, ignore the right half
            elif lst[mid] > x:
            high = mid - 1

            # means x is present in mid
            else:
                return mid

        # If we reach here, then the element was not present
        return -1


# Test list
lst = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(lst, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list")

_7 dua kali. Mengapa tidak menghitungnya satu kali dan menggunakan hasil yang sama lagi? . Berikut adalah artikel untuk mempelajari lebih lanjut tentang itu

Jangan lupa bahwa mengetahui kompleksitas waktu memungkinkan kita membangun algoritme yang lebih baik. Kami dapat menggunakan pengetahuan kami untuk meningkatkan algoritme karena kami tahu apa yang menyebabkan kompleksitas waktu yang lebih buruk atau lebih baik

Jika Anda ingin memvisualisasikan algoritme yang kami bahas dan lainnya, Anda dapat mengunjungi visualgo

Berikut adalah grafik di mana Anda dapat melihat kompleksitas waktu yang kami bahas

Terima kasih telah membaca dan saya harap ini membantu Anda

Jika Anda ingin melihat artikel saya yang lain dan melihat postingan tentang Python dan Pengembangan Backend, lihat Twitter dan Blog saya

Bagaimana Anda menemukan kompleksitas waktu suatu fungsi di Python?

— Buat variabel dan hemat waktu setelah algoritme dijalankan, sebut saja end1. — Kurangi akhir1 dengan awal1 (akhir1 — awal1) dan simpan selisihnya ke dalam variabel yang disebut runtime . Waktu proses ini adalah berapa lama waktu yang diperlukan untuk mengeksekusi fungsi/algoritma Anda.

Berapa kompleksitas waktu dari fungsi set di Python?

Kompleksitas waktu ini adalah O(len(s1) + len(s2)) di mana s1 dan s2 adalah dua himpunan yang kebutuhan penyatuannya . Persimpangan. - Ini dapat dilakukan melalui persimpangan () atau dan operator. Elemen Umum dipilih. Mereka mirip dengan iterasi atas daftar Hash dan menggabungkan nilai yang sama pada kedua Tabel.

Apa kompleksitas waktu dari suatu fungsi?

Kompleksitas waktu didefinisikan sebagai jumlah waktu yang dibutuhkan oleh algoritme untuk berjalan, sebagai fungsi dari panjang masukan . Ini mengukur waktu yang dibutuhkan untuk mengeksekusi setiap pernyataan kode dalam suatu algoritma. Itu tidak akan memeriksa total waktu eksekusi suatu algoritma.