Jaka jest złożoność pamięci std :: sort() i std :: sort_heap()?

Jak w tytule - jaka jest złożoność pamięci std::sort() i std::sort_heap()? (Ten ostatni wymaga std::make_heap() więc chciałbym wiedzieć, jego złożoność pamięci, jak również.)Jaka jest złożoność pamięci std :: sort() i std :: sort_heap()?

Próbowałem wyszukiwanie na tych stronach: http://www.cplusplus.com/reference/http://en.cppreference.com/w/ ale albo brakowało mi go albo oni tylko wspomnieć złożoność czasową. Czy złożoność pamięci wspomnianych funkcji jest określona w dowolnym miejscu (w standardzie C++ lub innym dokumencie)? A może to zależy od wdrożenia?

Źródło

2014-10-09 NPS

Wszystkie trzy algorytmy są na miejscu, tj. Dodatkowa pamięć to O (1). – user515430

Zgodnie z tym: http://stackoverflow.com/questions/1840121/which-type-sorting-is-used-in-the-function-sort 'std :: sort()' może używać 'introsorta' który z kolei używa 'quicksort', który nie jest na miejscu (stos wywołań rekursywnych). – NPS

Quicksort jest bardzo na miejscu. Dane nigdy nie są przenoszone do zewnętrznego magazynu danych. Dane nigdy nie są umieszczane na stosie. Parametry dotyczące miejsca w pojemniku można umieścić na stosie. Można spierać się o to, czy pamięć jest O (1), ale nie o to, że jest w miejscu. – user515430

Dla std::sort() znalazłem odpowiedź na Cboard, który dość dużo mówi:

Jakość kwestii wdrażania. Różne implementacje wykorzystują pamięć bardziej efektywnie niż inne implementacje. Poza tym standard umożliwia specjalizację dla std::sort dla różnych kategorii iteratorów, pozwalając implementacji na wybór pomiędzy kilkoma różnymi opcjami, o ile złożoność (czas) odpowiada wymaganiom. Podana złożoność nie jest czasem, ale liczbą porównań. Wdrożenie może wykonać operacje wymiany N³.

szczytowy pamięci dla większości wdrożeń std::sort byłyby podobne do głębokości rekursji i liczby zmiennych lokalnych przechowywanych na stosie na każdym poziomie rekurencji. Implementacja HP / Microsoft STL std::sort używa Quicksort do/dopóki nie wykryje, że poziom rekursji jest zbyt duży, w którym to przypadku przełącza się na sortowanie sterty. Jeśli rozmiar jest mały, na przykład 32 lub mniejszy, wówczas korzysta z programu Insertionsort.

Możesz zobaczyć porównanie algorytmów, w Wikipedii page i oszacować złożoność pamięci.

Podobno podejrzewam, że pozostałe dwa algorytmy należą do tego samego przypadku.

Źródło

2014-10-09 22:19:26 gsamaras

Podana złożoność nie jest czasem, ale liczbą porównań. Implementacja może wykonać operacje wymiany N^3. – dyp

Wierzę, że standard wymaga, aby 'std :: sort' był' O (n * log (n)) 'w czasie, chociaż nie mogę go teraz zacytować. – NPS

Zgadzam się z Dyp. NPS Nie udało mi się znaleźć czegoś, co mogłoby wspomóc Twój komentarz. – gsamaras

Jaka jest złożoność pamięci std :: sort() i std :: sort_heap()?

Odpowiedz

Powiązane problemy