Dane wejściowe: dodatnia liczba całkowita K i duży tekst. Tekst można w rzeczywistości postrzegać jako ciąg słów. Więc nie musimy się martwić, jak podzielić to na ciąg słów.
Wynik: Najczęstsze K słów w tekście.
Moje myślenie jest takie.
użyj tablicy Hash, aby zapisać częstotliwość wszystkich słów podczas przechodzenia przez całą sekwencję słów. W tej fazie kluczem jest „słowo”, a wartością jest „częstotliwość słów”. To zajmuje O (n) czasu.
sortować parę (słowo, częstotliwość słów); a kluczem jest „częstotliwość słów”. To zajmuje O (n * lg (n)) czasu przy normalnym algorytmie sortowania.
Po sortowaniu bierzemy tylko pierwsze K słów. To zajmuje O (K) czasu.
Podsumowując, całkowity czas wynosi O (n + n lg (n) + K) , Ponieważ K jest na pewno mniejsze od N, więc w rzeczywistości wynosi O (n lg (n)).
Możemy to poprawić. Właściwie chcemy tylko najlepszych słów K. Innymi słowy, częstotliwość nie dotyczy nas. Możemy więc użyć „częściowego sortowania sterty”. W kroku 2) i 3) nie zajmujemy się tylko sortowaniem. Zamiast tego zmieniamy go na
2 ') zbuduj stos par (słowo, częstotliwość słowa) z kluczem „częstotliwość słowa”. Zbudowanie sterty zajmuje O (n) czasu;
3 ') wyodrębnij górne K słów ze stosu. Każda ekstrakcja to O (lg (n)). Zatem całkowity czas wynosi O (k * lg (n)).
Podsumowując, to rozwiązanie kosztuje czas O (n + k * lg (n)).
To tylko moja myśl. Nie znalazłem sposobu na ulepszenie kroku 1).
Mam nadzieję, że niektórzy eksperci ds. Wyszukiwania informacji mogą rzucić więcej światła na to pytanie.