İki zaman karmaşıklığı ile sıkışıp kaldım. Sıralı dizi ile ikili arama yapmak için O (logN). Bu yüzden sıralanmamış bir dizi aramak için önce onu sıralamak zorundayız, böylece O (NlogN) olur. O zaman karmaşıklığı O (N) olarak veren ikili arama yapabiliriz, fakat O'nun (NlogN) olabileceğini okudum. Hangisi doğru?Sıralanmamış bir dizi için ikili aramanın zaman karmaşıklığı
İkili Arama "Sıralı" listeler içindir. Karmaşıklık O (logn).
İkili Arama, "sıralanmamış" listelerde çalışmıyor. Bu listeler için sadece ilk elemandan başlayarak düz bir arama yapın; Bu, O (n) 'nin karmaşıklığını verir. Diziyi MergeSort veya başka bir O (nlogn) algoritması ile sıralamak isterseniz, karmaşıklık O (nlogn) olur.
O (logn) < O (n) <
BinarySearch, dizinin biraz da olsa ayrılmasa bile çalışmaya devam edebilir. Not etmek güzel. – ofarooq
Sorunuzun cevabı sorunuzu kendisinde (nlogn) O. İlk önce listeyi sıralıyorsunuz. Listenizi hızlı veya birleştirme sıralama kullanarak sıralarsanız, karmaşıklık o (n log n) olur. Bölüm - 1 devraldı. Bir ikili arama yapmanın ikinci kısmı 'Sıralı liste' üzerinde yapılır. İkili aramanın karmaşıklığı o (log n). Bu nedenle, sonuçta programın karmaşıklığı o (n log n) kalır. Bununla birlikte, dizinin medyanını hesaplamak isterseniz, listeyi sıralamak zorunda değilsiniz. Doğrusal veya sıralı bir aramanın basit bir uygulaması size yardımcı olabilir.
Doğrusal aramanın zaman karmaşıklığı O(n) ve ikili arama O(log n) (log base-2) 'dir. Sıralanmamış bir dizimiz varsa ve bunun için ikili arama kullanmak istiyorsak, diziyi önce sıralamalıyız. Ve burada diziyi sıralamak ve sonra arama elemanına zaman harcamak için O(n logn) bir zaman harcamak zorundayız.
Bunlar iki ayrı işlemdir. İkili arama her zaman ** O (log n) ** olacaktır. – squiguy
Doğru, bir ikili arama, sıralanmamış bir dizi üzerinde çalışmayacak; Ancak, diziyi ikili aramayı gerçekleştirmek için sıralamanız gerekir. En azından son zamanlarda böyle öğrendim. – user2373448