Linear search (original) (raw)

About DBpedia

البحث الخطي أو البحث المتسلسل (بالإنجليزية: Liner search)‏ في علوم الحاسوب، هي طريقة لإيجاد قيمة في مجموعة أو قائمة والبحث يكون بفحص كل قيم المجموعة أو القائمة واحدا تلو الآخر حتى إيجاد القيمة المطلوبة أو انتهاء القائمة. البحث الخطي ما هو إلا حالة خاصة من خوارزمية أعم وهي خوارزمية البحث الشامل. بما أن البحث الخطي لا يفترض أي افتراضات قوية بشكل عام هنالك خورزميات يمكن أن تكون أفضل مثل خوارزمية البحث الثنائي أو دالة هاش.

Property Value
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
dbo:wikiPageID 18171 (xsd:integer)
dbo:wikiPageLength 7610 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1119777726 (xsd:integer)
dbo:wikiPageWikiLink dbr:Binary_search_algorithm dbr:Algorithm dbc:Search_algorithms dbr:Geometric_distribution dbr:Search_data_structure dbr:Subroutine dbr:Computer_science dbr:Time_complexity dbr:Linear_search_problem dbr:Record_(computer_science) dbr:Hash_table dbr:Asymptotic_complexity dbr:Big_O_notation dbr:Ternary_search dbr:Search_algorithm dbr:Sentinel_value dbr:List_(computing) dbr:Sort_(computing) dbr:Binary_search
dbp:averageTime dbr:Big_O_notation
dbp:bestTime dbr:Big_O_notation
dbp:class dbr:Search_algorithm
dbp:edition 2 (xsd:integer)
dbp:optimal Yes (en)
dbp:space O(1) iterative (en)
dbp:time dbr:Big_O_notation
dbp:volume 3 (xsd:integer)
dbp:wikiPageUsesTemplate dbt:= dbt:ISBN dbt:Math dbt:Multiple_issues dbt:One_source dbt:Refimprove dbt:Reflist dbt:Sfn dbt:Sfrac dbt:Short_description dbt:TAOCP dbt:PAGENAMEBASE dbt:Infobox_algorithm
dct:subject dbc:Search_algorithms
gold:hypernym dbr:Method
rdf:type dbo:Software yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms
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)
rdfs:label بحث خطي (ar) Lineární vyhledávání (cs) Lineare Suche (de) Γραμμική αναζήτηση (el) Búsqueda lineal (es) Pencarian linear (in) Ricerca sequenziale (it) Recherche séquentielle (fr) Linear search (en) 순차 검색 알고리즘 (ko) 線型探索 (ja) Lineair zoeken (nl) Przeszukiwanie liniowe (pl) Busca linear (pt) Линейный поиск (ru) Linjärsökning (sv) 线性搜索 (zh) Лінійний пошук (uk)
owl:sameAs freebase:Linear search yago-res:Linear search wikidata:Linear search dbpedia-ar:Linear search dbpedia-az:Linear search http://bn.dbpedia.org/resource/রৈখিক_অনুসন্ধান dbpedia-cs:Linear search dbpedia-da:Linear search dbpedia-de:Linear search dbpedia-el:Linear search dbpedia-es:Linear search dbpedia-fa:Linear search dbpedia-fi:Linear search dbpedia-fr:Linear search http://hi.dbpedia.org/resource/रैखिक_खोज dbpedia-hu:Linear search dbpedia-id:Linear search dbpedia-is:Linear search dbpedia-it:Linear search dbpedia-ja:Linear search dbpedia-ka:Linear search dbpedia-ko:Linear search dbpedia-nl:Linear search dbpedia-pl:Linear search dbpedia-pt:Linear search dbpedia-ru:Linear search dbpedia-simple:Linear search dbpedia-sk:Linear search dbpedia-sr:Linear search dbpedia-sv:Linear search dbpedia-uk:Linear search dbpedia-vi:Linear search dbpedia-zh:Linear search https://global.dbpedia.org/id/4wWVn
prov:wasDerivedFrom wikipedia-en:Linear_search?oldid=1119777726&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Linear_search
is dbo:wikiPageRedirects of dbr:Linear_search_algorithm dbr:Sequential_search
is dbo:wikiPageWikiLink of dbr:Quantum_complexity_theory dbr:List_of_algorithms dbr:Binary_search_algorithm dbr:Bisection_(software_engineering) dbr:Block_sort dbr:Best,_worst_and_average_case dbr:Index_of_combinatorics_articles dbr:Interpolation_search dbr:Analysis_of_algorithms dbr:Private_biometrics dbr:Quantum_algorithm dbr:Search_data_structure dbr:CoffeeScript dbr:Glossary_of_computer_science dbr:Consistent_hashing dbr:Control_table dbr:BASIC_interpreter dbr:Time_complexity dbr:Timsort dbr:Database_index dbr:Jump_search dbr:Linear_search_problem dbr:Linked_list dbr:Cycle_sort dbr:Find_first_set dbr:Dirhash dbr:Machine_epsilon dbr:Hash_table dbr:Self-organizing_list dbr:Ternary_search dbr:Associative_array dbr:Brute-force_search dbr:Search_algorithm dbr:Exponential_search dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Non-uniform_random_variate_generation dbr:Linear_search_algorithm dbr:Sequential_search
is owl:differentFrom of dbr:Line_search
is foaf:primaryTopic of wikipedia-en:Linear_search