Saya perlu menghitung kompleksitas waktu berjalan dari fungsi dalam n (misalnya O(n)), n adalah len(lst) , lst adalah variabel tipe daftar.
ini yang kupikirkan, benarkah? (Saya perlu menemukan batasan yang paling ketat!!!) 
Hitung kompleksitas fungsinya, hw dengan python
Jawaban (1)
Oke, ini soal yang cukup rumit, dan cukup menyenangkan untuk dijadikan pekerjaan rumah.
Pertama, jelas bahwa Anda harus membagi soal menjadi dua bagian, baik jika n lebih besar dari 100.000 atau tidak.
Jika n lebih besar dari 100.000:
Anda akan menjalankan loop terdalam maksimal 20.000 kali sekaligus (karena ketika j lebih besar dari 100.000, loop k Anda akan menghasilkan 0 iterasi). Jadi untuk setiap simulasi, untuk bagian n di atas 50.000 Anda akan melakukannya dengan tepat
jumlah loop. Memberikan
. Anda harus menambahkan waktu perhitungan pada bagian i ‹ 50 000 (n ‹ 100 000), yang dapat ditulis sebagai
,
yang memberikan 
.
Artinya di atas n = 100.000, soal Anda memiliki kompleksitas O(n) yang jelas dengan bagian konstan yang besarnya satu atau lebih lebih kecil dari bagian linier:
Bagian yang sulit terjadi ketika Anda mendapatkan di bawah n = 100.000. Di sini Anda dapat menulis
,
yang dapat diubah menjadi:
Fungsi ini menunjukkan kenaikan linier dengan penurunan kuadrat. Tebak dimana akarnya… (hampir) tepat di angka 100.000.
Menghitung jumlah dan meninggalkan bagian O(1), O(n) dan tidak penting, Anda mendapatkan:
.
Anda dapat melihat bahwa bagian kubiknya negatif, sehingga waktunya akan berada di bawah 0 untuk n-s yang besar. Namun Anda juga dapat melihat bahwa pada n = 100.000, bagian kuadratnya masih tiga kali lebih besar dari bagian kubik, dan fungsi maksimumnya ada pada n = 200.000. Jadi jangan khawatir, Anda tidak akan membahasnya saat-saat negatif, nyatanya Anda bahkan tidak akan mencapai hasil maksimal dari fungsi ini.
Bagaimana Anda bisa menafsirkannya? Dalam kasus terburuk, Anda memiliki kompleksitas O(n2). Namun Anda memiliki penurunan orde lebih tinggi, dan untuk n-s besar di bawah 100.000, Anda dapat melakukan jauh (maks. 33%) lebih baik daripada prediksi O(n2).
Jadi kesimpulannya:
- Jika n jauh lebih kecil dari 100.000: O(n2)
- Jika n mendekati, tetapi lebih kecil dari 100.000: lebih baik dari O(n2)
- Jika n lebih besar dari 100.000: O(n)
Saya memberikan contoh untuk mengukur apa yang terjadi. Saya menggunakan nomor yang berbeda (karena masalah awal Anda akan berjalan selamanya), jadi nilai ambang batas 100.000 Anda adalah 100 dalam kasus saya. Terlihat pada awalnya O(n2) berfungsi dengan baik, kemudian O(n2-n3) sesuai dengan kompleksitasnya, terakhir di atas 100 kita masuk ke bagian linier.
Dan untuk n-s yang besar (masih dengan ambang batas 100):
person
leeladam
schedule
07.12.2013
Saya tidak percaya ini benar. Di atas ambang batas, perulangan
k selesai dalam waktu yang konstan sedangkan perulangan i dan j berurutan n. Untuk nilai n yang besar, fungsi keseluruhannya adalah O(n^2). Di bawah ambang batas semua loop berorde n, membuat fungsi O(n^3). Saya menghitung waktu fungsi untuk nilai n yang besar dengan ambang batas 100 dan itu jelas tidak linier. i.imgur.com/i1Fglwc.png
- person Tim; 08.12.2013
@Tim: bukan hanya k, tetapi j loop yang selesai dalam waktu yang konstan untuk n › 10^5 ! Karena hanya bagian j in range(10^5) yang akan memberi Anda apa pun (yang merupakan konstanta), dan bagian j in range(10^5,n) tidak akan melakukan apa pun! Saya tidak dapat mereproduksi hasil Anda, saya mendapat ketergantungan linier sejauh 10.000 dengan ambang batas 100 (lihat jawaban yang diedit). Di sisi lain, perhatikan bahwa bagian n^3 Anda menurun, karena di loop dalam, j-s besar akan berjalan cepat, dan j-s kecil akan berjalan lambat! Jadi Anda mempunyai ketergantungan O(n3), tetapi ketergantungannya negatif, dan bagian utamanya hanya O(n2).
- person leeladam; 08.12.2013
for j in range(i) akan menskalakan secara linier - tidak selesai dalam waktu yang konstan. Sepertinya Anda menggunakan kode yang berbeda dengan penanya.
- person Tim; 08.12.2013
@Tim: Saya masih tidak setuju, tetapi sangat mungkin Anda benar. Anda harus menulis solusi Anda sebagai jawaban atas OP dan saya akan melakukan yang terbaik untuk memahaminya.
- person leeladam; 08.12.2013
k) konstan, semuanya harus O(n^2). Saya tidak yakin apakah itu konstan ketika linier ke suatu titik dan kemudian konstan... - person Tim schedule 07.12.2013