Saya baru-baru ini mempelajari pencarian biner .... Saya sangat terkesan dengan kompleksitas waktu O(log n), tetapi saya ragu bahwa untuk mendapatkan array yang diurutkan saya harus menerapkan operasi yang diurutkan yaitu minimum O(nlogn ) kompleksitas yang cukup lebih.

0
kunal_goyal 14 Maret 2017, 14:29

2 jawaban

Jawaban Terbaik

Jika Anda memiliki daftar yang tidak diurutkan (atau tidak dijamin untuk diurutkan), pencarian linier adalah cara yang harus dilakukan. Pencarian linier adalah O(n) sementara pengurutannya adalah O(nlog n), yang lebih buruk. Bahkan memeriksa apakah daftar diurutkan adalah O(n).

Jika Anda ingin mencari daftar hanya sekali, Anda lebih baik dengan pencarian linier. Jika Anda akan mencari beberapa kali, Anda mungkin mendapat manfaat dari menyortir daftar terlebih dahulu. Untuk mengetahui apa yang terbaik untuk kasus spesifik Anda, Anda harus menganalisis masalahnya.

0
klutt 14 Maret 2017, 12:08

Idenya adalah Anda mengurutkan daftar satu kali, dan menyimpan hasilnya. Pencarian selanjutnya adalah O(log n). Jadi kerumitan Anda di banyak penelusuran adalah (n log n) + S*log(n), dengan S adalah jumlah penelusuran yang akan Anda lakukan. Jika Anda tidak mengurutkan larik, beberapa penelusuran Anda akan dikenakan biaya O(S*n).

0
Jim Mischel 14 Maret 2017, 14:23