| dbo:abstract
|
- Lineární vyhledávání (také známé jako sekvenční vyhledávání) je vhodný na nalezení určité hodnoty v seznamu. Funguje na principu procházení všech prvků seznamu. Lineární vyhledávání má časovou složitost O(N). V případě náhodného rozložení je průměrně potřeba N/2 porovnání. Nejlepší případ nastane tehdy, když se hledaná hodnota nachází na prvním místě v seznamu, v tomto případě je potřeba pouze jedno porovnání. Nejhorší případ nastane tehdy, když se hodnota v seznamu vůbec nevyskytuje; v tom případě je potřeba N porovnání. Výhodou lineárního vyhledávání, oproti efektivnějším algoritmům jako například binární vyhledávání, je možnost použití i na neuspořádaných seznamech. V případě, že je potřeba vykonat na seznamu více vyhledávání, je vhodné použít efektivnější . Jedno z řešení je uspořádat seznam a použít binární vyhledávání. Další běžný postup je vybudovat hašovací tabulku a vyhledávat pomocí ní. (cs)
- البحث الخطي أو البحث المتسلسل (بالإنجليزية: Liner search) في علوم الحاسوب، هي طريقة لإيجاد قيمة في مجموعة أو قائمة والبحث يكون بفحص كل قيم المجموعة أو القائمة واحدا تلو الآخر حتى إيجاد القيمة المطلوبة أو انتهاء القائمة. البحث الخطي ما هو إلا حالة خاصة من خوارزمية أعم وهي خوارزمية البحث الشامل. بما أن البحث الخطي لا يفترض أي افتراضات قوية بشكل عام هنالك خورزميات يمكن أن تكون أفضل مثل خوارزمية البحث الثنائي أو دالة هاش. (ar)
- Γραμμική αναζήτηση (ή σειριακή αναζήτηση) ονομάζεται ένας αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο στοιχείο-κλειδί) σε μια δομή δεδομένων. Ο αλγόριθμος χρησιμοποιεί τη μέθοδο της τυφλής αναζήτησης (brute-force), καθώς δεν επιλέγει με κάποια κριτήρια μια υπο-περιοχή αναζήτησης, αλλά στηρίζεται στο γεγονός ότι αν ελέγξει όλα τα στοιχεία της δομής δεδομένων ένα προς ένα, τότε αν υπάρχει το στοιχείο κλειδί στη δομή θα το βρει. Είναι ο πιο απλός αλγόριθμος αναζήτησης και ο λιγότερο αποδοτικός. Ωστόσο, είναι ο απαραίτητος, αν η δομή δεν είναι ταξινομημένη. (el)
- Lineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt. Die Aufgabe besteht darin, ein Element in einer Liste oder einem Array mit n Elementen zu finden.Man geht dazu die Liste Element für Element durch, bis man es gefunden hat.Der Suchaufwand wächst linear mit der Anzahl der Elemente in der Liste. Die effizientere Binäre Suche kann nur bei geordneten Listen benutzt werden. Für ungeordnete Listen existiert mit Lazy Select noch ein randomisierter Algorithmus, der mit relativ hoher Wahrscheinlichkeit das x-te Element einer Liste bezüglich einer Ordnung schneller als in linearer Zeit finden kann. (de)
- En informática, la búsqueda lineal o la búsqueda secuencial es un método para encontrar un valor objetivo dentro de una lista. Ésta comprueba secuencialmente cada elemento de la lista para el valor objetivo hasta que es encontrado o hasta que todos los elementos hayan sido comparados. Búsqueda lineal es en tiempo el peor, y marca como máximo n comparaciones, donde n es la longitud de la lista. Si la probabilidad de cada elemento para ser buscado es el mismo, entonces la búsqueda lineal tiene una media de n/2 comparaciones, pero esta media puede ser afectado si las probabilidades de búsqueda para cada elemento varían. La búsqueda lineal es poco práctica porque otros algoritmos de búsqueda y esquemas, como el algoritmo de búsqueda binaria y Tabla hash, es significativamente más rápido buscando todo menos listas cortas. (es)
- In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n+1/2 comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists. (en)
- La recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. Elle consiste simplement à considérer les éléments de la liste les uns après les autres, jusqu'à ce que l'élément soit trouvé, ou que toutes les cases aient été lues. Elle est aussi appelée recherche par balayage. (fr)
- Dalam ilmu komputer, pencarian linear adalah sebuah algoritme pencarian, juga dikenal sebagai pencarian sekuensial, yang cocok untuk mencari sebuah nilai tertentu pada sebuah himpunan data. Algoritme ini beroperasi dengan memeriksa setiap elemen dari sebuah list sampai sebuah kecocokan ditemukan. Pencarian linear bekerja dalam O(n). Jika data terdistribusi secara acak, rata-rata ada n/2 pembandingan akan dilakukan. Kasus terbaik adalah ketika nilai yang dicari adalah elemen pertama dari list, kasus ini hanya memerlukan 1 pembandingan. Kasus terburuk adalah ketika nilai yang dicari tidak ada dalam list, yang memerlukan n pembadingan. Modul List pada pustaka standard mendefinisikan sebuah fungsi "mem" yang mengembalikan nilai true jika elemen yang diberikan berada dalam list atau false jika tidak. Fungsi ini dinyatakan sebagai berikut: let rec mem x = function [] -> false | h:: t -> h=x || mem x t Pencarian linear dapat diimplementasikan secara matematika dengan pencocokan pola: Mem[x_, {___, x_, ___}]:= TrueMem[_, _]:= False Pencarian linear dapat digunakan untuk mencari sebuah list tak berurut. Pencarian biner adalah pencarian yang lebih efisien yang dapat digunakan untuk mencari sebuah list berurut. Jika diperlukan beberapa kali pencarian, disarankan untuk menggunakan struktur data yang lebih efisien. Satu pendekatan adalah dengan mengurutkan terlebih dahulu kemudian gunakan pencarian biner untuk setiap pencarian. Cara lain yang lazim adalah membuat sebuah dan dilakukan pencariaan hash. (in)
- In informatica la ricerca sequenziale (o ricerca lineare) è un algoritmo utilizzabile per trovare un elemento in un insieme non ordinato. L'algoritmo controlla in sequenza gli elementi dell'insieme, arrestandosi quando ne trova uno che soddisfa il criterio di ricerca; non potendosi avvalere di alcun ordinamento tra gli elementi, l'algoritmo può concludere con certezza che l'insieme non contiene alcun elemento corrispondente solo dopo averli verificati tutti, richiedendo pertanto un numero di controlli, nel caso peggiore, pari alla cardinalità dell'intero insieme. (it)
- 순차 검색 알고리즘(sequential search algorithm), 또는 선형 검색 알고리즘(linear search algorithm)은 리스트에서 특정한 값을 찾는 알고리즘의 하나다. 이것은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 비효율적이지만, 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다. (ko)
- 線型探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。 個のデータから個のデータを検索する場合、時間計算量は 、空間計算量は である。 (ja)
- Przeszukiwanie liniowe (lub wyszukiwanie sekwencyjne) – najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze. Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do gdzie to całkowita liczba elementów. Algorytm ma złożoność Pseudokod: szukany_klucz := określona wartość;znaleziony_indeks := ?;for index := 1 to n do if tablica[index].klucz = szukany_klucz then begin {znaleziono element o podanym kluczu, zapamiętujemy pozycję w tablicy} znaleziony_indeks := index; break; { koniec iterowania} end; Wyszukiwanie liniowe może być jedynym sposobem wyszukiwania, gdy nie wiadomo niczego na temat kolejności kluczy. Dla dużej liczby danych algorytm jest bardzo nieefektywny, jednak gdy danych jest względnie mało, jest z powodzeniem stosowany (np. w tablicach mieszających, w których problem kolizji rozwiązuje się metodą łańcuchową). Dodatkowo jeśli wiadomo, że pewne klucze mogą być wyszukiwane częściej niż inne, można modyfikować kolejność danych, tak aby ponowne wyszukiwanie tego samego klucza kończyło się powodzeniem szybciej. Metoda ta nosi nazwę move-to-front, Donald Knuth wymienia w swojej pracy Sztuka programowania dwie strategie: 1.
* natychmiastowe przesunięcie znalezionego elementu na początek sekwencji, 2.
* przesunięcie tylko o jedną pozycję w stronę początku sekwencji. (pl)
- In de informatica is lineair zoeken (of sequentieel zoeken) een zoekalgoritme om een hoeveelheid data (meestal lijsten) te doorzoeken. Het algoritme begint bij het eerste element in een lijst en bekijkt elk volgend element totdat het gezochte element gevonden is. In het slechtste geval, , moeten alle elementen bekeken worden; de benodigde tijd is hierdoor O(n) waarbij n het aantal elementen in de lijst is. In het is het gezochte element het eerste element in de lijst waardoor er slechts 1 vergelijking nodig is. Wanneer de elementen willekeurig over de lijst verdeeld zijn, zijn er gemiddeld n/2 vergelijkingen nodig om het element te vinden. Lineair zoeken kan worden gebruikt om een ongesorteerde lijst te doorzoeken. Om een lange gesorteerde lijst te doorzoeken is bisectie (binair zoeken) het meest efficiënt. Als n groot is, kan het efficiënter zijn om de lijst eerst te sorteren (met een sorteeralgoritme) en dan binair zoeken te gebruiken in plaats van lineair zoeken. Een andere manier is een hashtabel maken en daarin waarden op te zoeken. (nl)
- Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequencial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmo. (pt)
- Linjärsökning är en sökningsalgoritm för att finna ett element i en datastruktur. Exempelvis, om du vill finna det största elementet i en lista behöver du söka genom listan. (sv)
- Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и, в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым. Если отрезок имеет длину N, то найти решение с точностью до можно за время . Т.о. асимптотическая сложность алгоритма — . В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют, только если отрезок поиска содержит очень мало элементов, тем не менее, линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Также линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума. В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично. (ru)
- Лінійний пошук - алгоритм послідовного пошуку знаходження заданого значення довільної функції на деякому її відрізку. Цей алгоритм є найпростішим алгоритмом пошуку і на відміну, наприклад, від двійкового пошуку, не накладає жодних обмежень на функцію і має просту реалізацію. Пошук значення функції здійснюється простим порівнянням чергового розглянутого значення (як правило пошук відбувається зліва направо, тобто від менших значень аргументу до більших) і, якщо значення збігаються (з тією або іншою точністю), то пошук вважається завершеним. Якщо відрізок має довжину N, то знайти рішення з точністю до можна за час . Таким чином асимптоматична складність алгоритму - . У зв'язку з малою ефективністю в порівнянні з іншими алгоритмами лінійний пошук зазвичай використовують лише тоді, коли відрізок пошукової системи містить дуже мало елементів, однак лінійний пошук не вимагає додаткової пам'яті або обробки/аналізу функції, так що може працювати в потоковому режимі при безпосередньому отриманні даних з будь-якого джерела. Так само, лінійний пошук часто використовується у вигляді лінійних алгоритмів пошуку максимуму/мінімуму. Як приклад можна розглянути пошук значення функції на множині цілих чисел, представленої в таблиці. (uk)
- 在计算机科学中，线性搜索或顺序搜索是一种寻找某一特定值的搜索算法，指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。是最简单的一种搜索算法。 (zh)
|
| rdfs:comment
|
- البحث الخطي أو البحث المتسلسل (بالإنجليزية: Liner search) في علوم الحاسوب، هي طريقة لإيجاد قيمة في مجموعة أو قائمة والبحث يكون بفحص كل قيم المجموعة أو القائمة واحدا تلو الآخر حتى إيجاد القيمة المطلوبة أو انتهاء القائمة. البحث الخطي ما هو إلا حالة خاصة من خوارزمية أعم وهي خوارزمية البحث الشامل. بما أن البحث الخطي لا يفترض أي افتراضات قوية بشكل عام هنالك خورزميات يمكن أن تكون أفضل مثل خوارزمية البحث الثنائي أو دالة هاش. (ar)
- Γραμμική αναζήτηση (ή σειριακή αναζήτηση) ονομάζεται ένας αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο στοιχείο-κλειδί) σε μια δομή δεδομένων. Ο αλγόριθμος χρησιμοποιεί τη μέθοδο της τυφλής αναζήτησης (brute-force), καθώς δεν επιλέγει με κάποια κριτήρια μια υπο-περιοχή αναζήτησης, αλλά στηρίζεται στο γεγονός ότι αν ελέγξει όλα τα στοιχεία της δομής δεδομένων ένα προς ένα, τότε αν υπάρχει το στοιχείο κλειδί στη δομή θα το βρει. Είναι ο πιο απλός αλγόριθμος αναζήτησης και ο λιγότερο αποδοτικός. Ωστόσο, είναι ο απαραίτητος, αν η δομή δεν είναι ταξινομημένη. (el)
- La recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. Elle consiste simplement à considérer les éléments de la liste les uns après les autres, jusqu'à ce que l'élément soit trouvé, ou que toutes les cases aient été lues. Elle est aussi appelée recherche par balayage. (fr)
- In informatica la ricerca sequenziale (o ricerca lineare) è un algoritmo utilizzabile per trovare un elemento in un insieme non ordinato. L'algoritmo controlla in sequenza gli elementi dell'insieme, arrestandosi quando ne trova uno che soddisfa il criterio di ricerca; non potendosi avvalere di alcun ordinamento tra gli elementi, l'algoritmo può concludere con certezza che l'insieme non contiene alcun elemento corrispondente solo dopo averli verificati tutti, richiedendo pertanto un numero di controlli, nel caso peggiore, pari alla cardinalità dell'intero insieme. (it)
- 순차 검색 알고리즘(sequential search algorithm), 또는 선형 검색 알고리즘(linear search algorithm)은 리스트에서 특정한 값을 찾는 알고리즘의 하나다. 이것은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 비효율적이지만, 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다. (ko)
- 線型探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。 個のデータから個のデータを検索する場合、時間計算量は 、空間計算量は である。 (ja)
- Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequencial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmo. (pt)
- Linjärsökning är en sökningsalgoritm för att finna ett element i en datastruktur. Exempelvis, om du vill finna det största elementet i en lista behöver du söka genom listan. (sv)
- 在计算机科学中，线性搜索或顺序搜索是一种寻找某一特定值的搜索算法，指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。是最简单的一种搜索算法。 (zh)
- Lineární vyhledávání (také známé jako sekvenční vyhledávání) je vhodný na nalezení určité hodnoty v seznamu. Funguje na principu procházení všech prvků seznamu. Lineární vyhledávání má časovou složitost O(N). V případě náhodného rozložení je průměrně potřeba N/2 porovnání. Nejlepší případ nastane tehdy, když se hledaná hodnota nachází na prvním místě v seznamu, v tomto případě je potřeba pouze jedno porovnání. Nejhorší případ nastane tehdy, když se hodnota v seznamu vůbec nevyskytuje; v tom případě je potřeba N porovnání. (cs)
- Lineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt. Die Aufgabe besteht darin, ein Element in einer Liste oder einem Array mit n Elementen zu finden.Man geht dazu die Liste Element für Element durch, bis man es gefunden hat.Der Suchaufwand wächst linear mit der Anzahl der Elemente in der Liste. Die effizientere Binäre Suche kann nur bei geordneten Listen benutzt werden. (de)
- En informática, la búsqueda lineal o la búsqueda secuencial es un método para encontrar un valor objetivo dentro de una lista. Ésta comprueba secuencialmente cada elemento de la lista para el valor objetivo hasta que es encontrado o hasta que todos los elementos hayan sido comparados. (es)
- In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. (en)
- Dalam ilmu komputer, pencarian linear adalah sebuah algoritme pencarian, juga dikenal sebagai pencarian sekuensial, yang cocok untuk mencari sebuah nilai tertentu pada sebuah himpunan data. Algoritme ini beroperasi dengan memeriksa setiap elemen dari sebuah list sampai sebuah kecocokan ditemukan. Pencarian linear bekerja dalam O(n). Jika data terdistribusi secara acak, rata-rata ada n/2 pembandingan akan dilakukan. Kasus terbaik adalah ketika nilai yang dicari adalah elemen pertama dari list, kasus ini hanya memerlukan 1 pembandingan. Kasus terburuk adalah ketika nilai yang dicari tidak ada dalam list, yang memerlukan n pembadingan. (in)
- In de informatica is lineair zoeken (of sequentieel zoeken) een zoekalgoritme om een hoeveelheid data (meestal lijsten) te doorzoeken. Het algoritme begint bij het eerste element in een lijst en bekijkt elk volgend element totdat het gezochte element gevonden is. (nl)
- Przeszukiwanie liniowe (lub wyszukiwanie sekwencyjne) – najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze. Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do gdzie to całkowita liczba elementów. Algorytm ma złożoność Pseudokod: (pl)
- Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и, в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым. (ru)
- Лінійний пошук - алгоритм послідовного пошуку знаходження заданого значення довільної функції на деякому її відрізку. Цей алгоритм є найпростішим алгоритмом пошуку і на відміну, наприклад, від двійкового пошуку, не накладає жодних обмежень на функцію і має просту реалізацію. Пошук значення функції здійснюється простим порівнянням чергового розглянутого значення (як правило пошук відбувається зліва направо, тобто від менших значень аргументу до більших) і, якщо значення збігаються (з тією або іншою точністю), то пошук вважається завершеним. (uk)
|
