Salin prompt ini ke Console pengembang kami untuk mencobanya sendiri!

Content
SystemTugas Anda adalah menganalisis fungsi atau algoritma yang diberikan dan menghitung kompleksitas waktunya menggunakan notasi Big O. Jelaskan penalaran Anda langkah demi langkah, menjelaskan bagaimana Anda sampai pada kompleksitas waktu akhir. Pertimbangkan skenario terburuk saat menentukan kompleksitas waktu. Jika fungsi atau algoritma berisi beberapa langkah atau perulangan bersarang, berikan kompleksitas waktu untuk setiap langkah dan kemudian berikan kompleksitas waktu keseluruhan untuk seluruh fungsi atau algoritma. Asumsikan setiap fungsi bawaan atau operasi yang digunakan memiliki kompleksitas waktu O(1) kecuali ditentukan lain.
Userdef example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k)

​
Contoh output

Untuk menganalisis kompleksitas waktu dari fungsi example_function(n) yang diberikan, kita akan memecahnya menjadi beberapa langkah dan mempertimbangkan skenario terburuk.

Langkah 1: Menganalisis perulangan pertama

for i in range(n):
   print(i)

Perulangan ini beriterasi sebanyak n kali dan melakukan operasi waktu konstan (print(i)) dalam setiap iterasi. Oleh karena itu, kompleksitas waktu dari langkah ini adalah O(n).

Langkah 2: Menganalisis perulangan bersarang

for j in range(n):
    for k in range(n):
        print(j, k)

Perulangan luar beriterasi sebanyak n kali, dan untuk setiap iterasi, perulangan dalam juga beriterasi sebanyak n kali. Dalam setiap iterasi perulangan dalam, operasi waktu konstan (print(j, k)) dilakukan. Oleh karena itu, kompleksitas waktu dari perulangan bersarang adalah O(n * n) = O(n^2).

Langkah 3: Menggabungkan kompleksitas waktu
Fungsi example_function(n) terdiri dari dua langkah: perulangan pertama dan perulangan bersarang. Kompleksitas waktu keseluruhan adalah jumlah dari kompleksitas waktu setiap langkah.

Kompleksitas waktu perulangan pertama: O(n)
Kompleksitas waktu perulangan bersarang: O(n^2)

Untuk menentukan kompleksitas waktu keseluruhan, kita mempertimbangkan suku dominan, yaitu suku dengan tingkat pertumbuhan tertinggi. Dalam kasus ini, O(n^2) mendominasi O(n).

Oleh karena itu, kompleksitas waktu keseluruhan dari fungsi example_function(n) adalah O(n^2).

Dalam skenario terburuk, ketika n besar, perulangan bersarang akan mendominasi waktu eksekusi, dan fungsi akan memiliki kompleksitas waktu kuadratik.

​
Permintaan API

Was this page helpful?

Pembuat merekPengklasifikasi ulasan