https://www.techiedelight.com/find-pair-with-given-sum-array/
Czy w trzecim rozwiązaniu to jest na pewno złożoność O(n)?
Przecież on tam używa find() które w najgorszym przypadku przeszuka i tak całą unordered_map?
#programowanie
Czy w trzecim rozwiązaniu to jest na pewno złożoność O(n)?
Przecież on tam używa find() które w najgorszym przypadku przeszuka i tak całą unordered_map?
#programowanie
- Najlepsze
- Wszystkie komentarze
konto usunięte
2
@qopeq: map to słownik, w którym użycie find zajmuje O(1) niezależnie ile znajduje się w nich par klucz wartość. W najgorszym wypadku pętla (nie na słowniku map ale na tablicy arr) wykona się n razy zatem złożoność wynosi O(n)
Hadzik
1
@qopeq: oczekiwana złożoność przeszukiwania hashmapy to O(1)
qopeq Autor
0
@qopeq: już nie ważne :) https://thispointer.com/what-is-hashing-and-hash-table/
qopeq Autor
0
@Hadzik @p0vnedu :dzięki
