Wpisany przez Tomasz Lubiński
piątek, 04 września 2009 19:39
Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej element zadany element x. Niech będzie to tablica a o indeksach od 1 do n. Czyli kolejne jej elementy oznaczymy: a[1], a[2], a[3], ..., a[n-1], a[n].
By odnaleźć element x podejmiemy następujące kroki:
Operację odnajdowania elementu w tablicy możemy zapisać następującym schematem blokowym:
Algorytm ten ma złożoność obliczeniową wynoszącą O(n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób liniowy wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. To znaczy, że czas potrzebny na wyszukanie dwa razy większej liczby elementów wzrośnie dwukrotnie.
Przykład:
Niech będzie dana tablica 5-elementowa, a = {4, 6, 2, 1, 3}.
Poszukajmy w niej element x = 2.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 2, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 2, przechodzimy do kolejnego elementu,
a[3] = x? 2 jest równe 2, zatem znaleźliśmy szukany element pod indeksem 3,
Poszukajmy teraz element x = 5.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 5, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 5, przechodzimy do kolejnego elementu,
a[3] = x? 2 nie jest równe 5, przechodzimy do kolejnego elementu,
a[4] = x? 1 nie jest równe 5, przechodzimy do kolejnego elementu,
a[5] = x? 3 nie jest równe 5, przechodzimy do kolejnego elementu,
To już koniec tablicy, zatem nie ma w niej elementu równego 5.
Przykład w JavaScript:
By odnaleźć element x podejmiemy następujące kroki:
- przejdziemy po kolejnych elementach tablicy, jeżeli dany element tablicy jest równy x to odnaleźliśmy szukany element i kończymy szukanie,
- jeżeli doszliśmy do końca tablicy to oznacza że zadanego elementu x nie ma w naszej tablicy.
Operację odnajdowania elementu w tablicy możemy zapisać następującym schematem blokowym:
Algorytm ten ma złożoność obliczeniową wynoszącą O(n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób liniowy wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. To znaczy, że czas potrzebny na wyszukanie dwa razy większej liczby elementów wzrośnie dwukrotnie.
Przykład:
Niech będzie dana tablica 5-elementowa, a = {4, 6, 2, 1, 3}.
Poszukajmy w niej element x = 2.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 2, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 2, przechodzimy do kolejnego elementu,
a[3] = x? 2 jest równe 2, zatem znaleźliśmy szukany element pod indeksem 3,
Poszukajmy teraz element x = 5.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 5, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 5, przechodzimy do kolejnego elementu,
a[3] = x? 2 nie jest równe 5, przechodzimy do kolejnego elementu,
a[4] = x? 1 nie jest równe 5, przechodzimy do kolejnego elementu,
a[5] = x? 3 nie jest równe 5, przechodzimy do kolejnego elementu,
To już koniec tablicy, zatem nie ma w niej elementu równego 5.
Przykład w JavaScript:
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | C# | MS Visual Studio .net |  | |
 / 0 |
| Tomasz Lubiński | C/C++ |  | |
/ 0 | |
| Albatross201 | C/C++ | C++ | | |
/ 0 |
| Marian | C/C++ | C++ | | |
/ 0 |
| Krzysztof Sośnierz | C/C++ | C++ templates | | |
/ 0 |
| Tomasz Lubiński | Delphi/Pascal |  | |
 / 3 | |
| Tomasz Lubiński | Java |  | |
/ 0 | |
| Jakub Konieczny | Java Block |  | |
/ 0 | |
| Dominik Goździuk | Java Script |  | |
/ 0 | |
| Dominik Goździuk | Perl |  | |
/ 0 | |
| Dominik Goździuk | Php |  | |
/ 0 | |
| Jakub Konieczny | Python |  | |
/ 0 |
Poprawiony: niedziela, 04 marca 2012 15:08