Jaka byłaby najmniejsza i największa liczba porównań w nieposortowanej tablicy, która mogłaby mieć również duplikaty elementów?Wyszukiwanie nieposortowanej tablicy
Rozumiem, że znalezienie czegokolwiek w nieposortowanej tablicy jest problemem O (n). Ale czy to prawda, jeśli tablica zawiera również duplikaty?
Przez duplikaty elementów mam na myśli elementy, które występują więcej niż jeden raz w danej tablicy.
Jako ogólna zasada, kiedy mówimy o asymptotycznej złożoności, która ignoruje stałe takie jak O (n), nie ma znaczenia, czy masz dwa razy więcej pracy, trzy razy więcej pracy itd. Dlatego problem, który jest O (n) pozostaje w tym scenariuszu O (n).
W tym szczególnym problemie, posiadanie duplikatów w nieposortowanej tablicy nie przyspiesza procesu wyszukiwania elementu. Oczywiście, jeśli element jest 10 razy w macierzy, prawdopodobnie byłby 10 razy szybszy (średnio), ale tak długo, jak długo nie zależy to od n, nie zmienia złożoności.
Pomysł polega na tym, że musisz przejść całą tablicę od początku do końca, ponieważ jest ona nieposortowana. Oznacza to, że patrzysz na O (n) - liniowy ruch elementów. Bez względu na to, czy szukany jest na pozycji 0, pozycji 8, czy pozycji n-1, musisz przejść przez tablicę, aby ją znaleźć.
Teraz, jeśli istnieją prawdopodobnie duplikaty w tablicy, jedyną różnicą jest to, że możesz znaleźć więcej niż jedno wystąpienie wartości. Jeśli szukasz ich wszystkich lub tylko pierwszego, wciąż jest to sytuacja O (n). Duplikaty nie zmieniają złożoności.
Najlepszy przypadek - znajdziesz go (zakładając, że musisz go znaleźć) przy pierwszym porównaniu.
Najgorszy przypadek - nie ma duplikatów dla podanej wartości i jest to ostatni sprawdzany - n-te porównanie.
Jeśli musisz znaleźć WSZYSTKIE duplikaty, zawsze będzie to n porównań, ponieważ musisz odwiedzić każdy element w nieposortowanej tablicy.
Czas O(n) jest prawdziwy, nawet jeśli występują zduplikowane elementy. Powinieneś zapoznać się z big-oh notation.
W najgorszym przypadku rozważ tę tablicę: 1, 1, 1, 1, ..., 1, 1, 2. Wyszukiwanie 2 będzie wymagało dokładnie n porównań, jeśli zaczniesz od pierwszego elementu, więc posiadanie duplikatów w ogóle nie pomogło. Gdybyś szukał 1, znalazłbyś to w jednym porównaniu, ale są wejścia różnych elementów, dla których możesz również znaleźć element w jednym porównaniu, jeśli masz szczęście, więc duplikaty naprawdę nie Znacznie dużo, z wyjątkiem tego, że masz większe szanse na szczęście i znalezienie elementu docelowego w mniejszej liczbie kroków. Jednak nadal będzie to O(n).
Prawie zawsze są najlepsze przypadki i najgorsze przypadki. Praktyczna wydajność większości algorytmów zawsze zależy od danych wejściowych, notacja big-oh daje tylko niejasne pojęcie o tym, jak będzie działał algorytm. Nie oznacza to, że notacja asymptotyczna jest bezużyteczna, tylko że nie zawsze jest całkowicie dokładna, ponieważ istnieją stałe stałe, które powodują różnicę w praktyce.
Jeśli masz wątpliwości co do wydajności, uruchom własne testy porównawcze.
Jaki byłby najmniejszy i największy liczbę porównań w niesegregowanych tablicy które mogłyby mieć zduplikowane elementy, jak również?
Jeśli szukasz pojedynczej określonej wartości, wówczas najmniejsza i największa liczba porównań będzie wynosić odpowiednio 1 i n. Jeśli wiadomo, że wartość znajduje się w tablicy, a szukasz jej tylko lokalizacji, możesz odejść od porównań n-1.
I sprawę, że znalezienie nic w niesegregowanych tablicy jest O (n) problemu. Ale czy jest to prawda, jeśli tablica zawiera także duplikaty elementów ?
Tak, nadal jest to O (n).
Załóżmy, że obecność duplikatów oznacza, że wyszukiwanie czasu jest przeciętnie o połowę mniejsze. To duża redukcja, ale nie wpływa to na czas O (n). Big-O nie jest przypadkiem przeciętnym, jest to najgorszy przypadek, a najgorszy przypadek się nie zmienia. A podział n przez stały czynnik w ogóle nie wpływa na czas big-O.
Czy jesteś pewien, że "Big-O nie jest przypadkiem przeciętnym, to najgorszy przypadek"? Z tego, co wiem, Big-O wcale nie jest przypadkiem. – Lazer
@Lazer - Tak. Big-O służy do wskazania asymtotycznego górnego ograniczenia funkcji (w ramach stałego współczynnika). Jeśli byłby to wskaźnik średniej lub najlepszego przypadku, to nie może być górną granicą. –
Jak widzę nie powinno być 2n porównania
for (int i=0; i<n; i++)
if (a[i]==ele)
break
else
continue;
więc istnieją dwa porównania (i<n) i (a[i]==ele) zrobić n razy w najgorszym przypadku. Dlatego porównania 2n. Jeśli jest jakiś sposób, w jaki można zmniejszyć liczbę i<n, nie wiem jak.
Tak jak wszyscy inni zgadzam się na nieposortowaną tablicę bez duplikatów, wyczerpujące wyszukiwanie liniowe będzie O (n).
Jeśli dozwolone są duplikaty, algorytm pozostaje tylko O (n) przy założeniu, że prawdopodobieństwo powielenia dowolnego elementu jest równomiernie rozłożone.
Jeśli istnieje funkcja gęstości prawdopodobieństwa opisująca rozkład duplikatów, algorytm wyszukiwania będzie prawdopodobnie mniejszy niż O (n) w zależności od funkcji gęstości prawdopodobieństwa.
Liczba porównań zależy od tego, czego szukasz. Czy to konkretny element? Pierwszy element, który jest duplikatem? Pełna posortowana wersja tablicy? – Pops
Witamy w SO! Pozwól, że dam ci pierwszy upominek na temat używania pracy domowej i napisania czystego, zrozumiałego pytania (otrzymujemy niefortunną ilość _plzsendtehcodez_). – Pops