Zakładając, że jest ustalony (tak jak robią to oba połączone wykłady), wówczas twoje algorytmy określą, czy twoje obliczenia będą działać w środowisku uruchomieniowym O ( n d + k n ), czy w środowisku uruchomieniowym O ( n d k ) .kO(nd+kn)O(ndk)
Najpierw rozważmy algorytm czasu wykonania :O(nd+kn)
- Zainicjuj dla wszystkich obserwacji i w zestawie treningowymselectedi=0i
- Dla każdej obserwacji zestawu treningowego oblicz d i s t i , odległość od nowej obserwacji do obserwacji zestawu treningowego iidistii
- Dla do k : Zapętlaj wszystkie obserwacje zestawu treningowego, wybierając indeks i o najmniejszej wartości d i s t i dla którego s e l e c t e d i = 0 . Wybierz tę obserwację, ustawiając s e l e c t e d i = 1 .j=1kidistiselectedi=0selectedi=1
- Zwraca wybranych indeksówk
Każde obliczenie odległości wymaga czasu wykonania , więc drugi krok wymaga czasu wykonania O ( n d ) . Dla każdej iteracji w trzecim kroku wykonujemy pracę O ( n ) , zapętlając obserwacje zestawu treningowego, więc ogólny krok wymaga pracy O ( n k ) . Pierwszy i czwarty krok wymagają tylko pracy O ( n ) , więc otrzymujemy środowisko wykonawcze O ( n d + k n ) .O(d)O(nd)O(n)O(nk)O(n)O(nd+kn)
Rozważmy teraz algorytm wykonawczy :O(ndk)
- Zainicjuj dla wszystkich obserwacji i w zestawie treningowymselectedi=0i
- Dla do k : Zapętl wszystkie obserwacje zestawu treningowego i oblicz odległość d pomiędzy obserwacją wybranego zestawu treningowego a nową obserwacją. Wybierz indeks i o najmniejszej wartości d, dla której s e l e c t e d i = 0 . Wybierz tę obserwację, ustawiając s e l e c t e d i = 1 .j=1kdidselectedi=0selectedi=1
- Zwraca wybranych indeksówk
Dla każdej iteracji w drugim kroku obliczamy odległość między nową obserwacją a każdą obserwacją zestawu treningowego, wymagając pracy dla iteracji, a zatem O ( n d k ) pracy ogólnej.O(nd)O(ndk)
Różnica między tymi dwoma algorytmami polega na tym, że pierwsze wstępnie oblicza i przechowuje odległości (wymagające dodatkowej pamięci ), a drugie nie. Biorąc jednak pod uwagę, że już przechowujemy cały zestaw szkoleniowy, wymagający pamięci O ( n d ) , a także wektora s e l e c t e d , wymagającego pamięci O ( n ) , pamięć dwóch algorytmów jest asymptotycznie podobnie. W rezultacie lepszy asymptotyczny czas działania dla k > 1 sprawia, że pierwszy algorytm jest bardziej atrakcyjny.O(n)O(nd)selectedO(n)k>1
Warto zauważyć, że możliwe jest uzyskanie środowiska wykonawczego za pomocą ulepszenia algorytmu:O(nd)
- Dla każdej obserwacji zestawu treningowego oblicz d i s t i , odległość od nowej obserwacji do obserwacji zestawu treningowego iidistii
- Uruchom algorytm szybkiego wyboru, aby obliczyć najmniejszą odległość w środowisku wykonawczym O ( n )kthO(n)
- Zwróć wszystkie wskaźniki nie większe niż obliczona najmniejsza odległośćkth
Podejście to wykorzystuje fakt, że istnieją wydajne podejścia do znalezienia najmniejszej wartości w nieposortowanej tablicy.kth
quickselect
.