Posortuj serię liczb n pomiędzy [0,2k], gdzie między każdą parą istnieje: | Ai-Aj |> = k/n

Question

Niechbędzie liczbą rzeczywistą między [0,2k] (k jest stała). Wiadomo, że dla dowolnej pary Ai,AJ następnie |Ai-Aj|>=k/n,

Opisać algorytm sortujący liczby w najgorszym przypadku runtime O(n) runtime.

Wiem, że odpowiedź powinna być sortowana przez wiadro. Nie mogę zrozumieć, dlaczego, A jeśli tak, to w jaki sposób wybrać odpowiednią liczbę kubełków? Jak naprawdę pomaga |Ai-Aj|>=k/n?

Answer 1

Warunek | A _i - Aj | ≥ k/n oznacza, że ​​jeśli dzieli się przedział [0, 2k] na 2n różnych wiader (z których każdy ma rozmiar 2k/2n = k/n), w każdym zakresie może znajdować się co najwyżej jedna liczba (z wyjątkiem liczby znajdują się w punktach końcowych kubełków.) Jeśli tworzysz pojemniki mocniej (powiedzmy, tworząc wiadra 3n), wtedy każdy pojemnik ma rozmiar mniejszy niż k/n, a zatem może zawierać najwyżej jedną liczbę.

Można następnie posortować liczby stosując algorytm wiadro sortowania:

• utworzyć tablicę 3n czerpaki, z których każdy reprezentuje przedziale [(2k/3N) i (2k/3n) (I + 1))
• Dla każdego numeru:
  • Podziel tę liczbę przez (2k/3n), aby określić, w którym wiadrze umieścić.
  • Umieść numer w tym wiadrze.
• Dla każdego segmentu:
  • Jeśli że wiadro jest niepusty, zapisz numer w tym wiadrze do tablicy wynikowej.

pierwszy etap trwa O (n), gdyż podczas tworzenia tablicę wielkości 3n. Kolejny krok zajmuje czas O (n), ponieważ odwiedzasz każdą z liczb O (n) i wykonujesz O (1) przy każdym kroku. Ostatni etap zajmuje również O (n) czas, ponieważ odwiedzasz w sumie 3n wiader.

Mam nadzieję, że to pomoże!