АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Лінійний пошук

Читайте также:
  1. Алгоритм 4.3. Діагностичний і лікувальний (перша медична допомога) пошук при струсі мозку.
  2. Алгоритми пошуку
  3. Базис. Лінійний підпростір. Ранг матриці
  4. Бінарний пошук
  5. Диференціація та творчо – пошуковий характер завдань (на уроці української мови)
  6. Контекстний пошук і заміна символів у тексті
  7. Лінійний гармонічний осцилятор
  8. Метод пошуку з бар’єром
  9. Напрями діяльності міжнародного співтовариства в пошуках виходу з глобальної гуманітарної кризи
  10. Підряд на проектні та пошукові роботи
  11. Пошук, заміна і фільтрація даних

Пошук, сортування

Та поняття складності у програмуванні

http://www.mindmeister.com/es/79132224/_

 

ПОШУК

Розглянемо різні методи пошуку елементу у деякому масиві.

В залежності від організації інформації, (впорядковані, невпорядковані дані) використовують різні методи пошуку.

Послідовниий пошук

Лінійний пошук

Описаний спосіб пошуку називаєють лінійним, простим або послідовним.

Сутність методу полягає в тому, що елементи масиву послідовно порівнюються із зразком (ключем) пошуку. Якщо має місце співпадання, то пошук закінчується. Інакше здійснюється перехід до наступного елементу. Отже, пошук припиняється або при досягненні кінця масиву, або при знаходженні заданого елемента. Даний та наступні алгоритми розглядаються для випадку, коли елементи масиву не повторюються.

                     

Оскільки наявність та місцезнаходження елементу наперед невідомі, то для практичної реалізації алгоритму потрібно застосувати цикл з передумовою. Пошук елементу масиву проводять поки не знайдено відповідний елемент, або поки не дійдемо до кінця масиву.

 

Час пошуку за цим алгоритмом залежить від кількості n елементів масиву.

Узагальнимо присвоювання та операції над значеннями скалярних типів (порівняння, додавання, множення тощо) терміном елементарна дія. Будемо вважати, що на виконання кожної елементарної дії витрачається скінченний обмежений проміжок часу, незалежний від конкретних операндів. За такого припущення час виконання програми (підпрограми) прямо пропорційний кількості елементарних дій у процесі виконання.

Очевидно, що кількість елементарних дій прямо пропорційна кількості порівнянь A[i]<> x. В найгіршому випадку з ключем порівнюються всі елементи массиву, тоді кількість перевірок дорівнює - N. Середня кількість перевірок у разі успіху - N/2.

Звідси максимальна кількість дій та найбільший час виконання функції прямо (лінійно) пропорційні n, і найбільший час пошуку t 1 є лінійною функцією від кількості елементів масиву. Лінійну залежність часу від кількості елементів, тобто довжини n, будемо позначати символом "O": t 1 = O(n).

Єдина модифікація, яку можна зробити, - позбавитися перевірки номера (i <= N) за рахунок збільшення масиву на один елемент у кінці, ключ якого буде рівним x (та званий "бар'єр").

 


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)