[0,2k] arasında bir dizi n sayısının sıralanması, Her bir çiftin bulunduğu yer: | Ai-Aj |> = k/n

Question

A1,A2,...,An[0,2k] arasındaki gerçek sayılar olsun (k sabittir). Daha sonra Ai,AJ|Ai-Aj|>=k/n herhangi çifti,

için O(n) çalışma zamanı en kötü durumda sayılar sıralanırken bir algoritma tarif edin biliniyor.

Bunun cevabın kova-sıralama olması gerektiğini biliyorum. Nedenini anlayamıyorum Ve eğer öyleyse, doğru miktarda kova nasıl seçerim? |Ai-Aj|>=k/n aslında nasıl yardımcı olur?

Answer 1

Durum - A _i - A _j | ≥ k/n, [0, 2k] aralığını 2n farklı kovaya bölerseniz (her biri boyutu 2k/2n = k/n olan), her bir aralıkta en fazla bir sayı olabilir (Rakamlar, kepçelerin uç noktalarındadır.) Kepçeleri daha sıkı bir şekilde oluşturursanız (3n kepçeleri oluşturarak), her kepçenin boyutu k/n'den küçüktür ve bu nedenle en fazla bir sayı içerebilir.

Daha sonra bir paket sıralama algoritması kullanılarak sıralamak olabilir:

• 3n kova, bir dizi, her bir aralık [(2k/3n) temsil eden oluşturma inositol, (2k/3n) (i + 1)), her bir dizi için
• : numarası (2k/3N) ile yerleştirmek için olan kepçe belirlemek için
  • Böl.
  • Numarayı bu kutuya yerleştirin. her bir bölüm için
• : bu kova boş olmayan ise
  • , sonuç diziye bu kova numarasını yazın. Eğer boyutu 3N bir dizi oluştururken yana

ilk adım, O (n) bir zaman alır. Bir sonraki adım O (n) zamanını alır, çünkü O (n) sayılarının her birini bir kez ziyaret edersiniz ve her adımda O (1) çalışır. Son adım ayrıca toplam 3n kovaları ziyaret ettiğinizden O (n) süreyi de alır.

Bu yardımcı olur umarız!