Линейный поиск

Одна из основных задач при работе с алгоритмами — оценка эффективности программы и поиск наиболее экономичного подхода. Самое простое и поверхностное решение этой задачи — написать программу и замерить время её выполнения. Программа тормозит? Изменить программу, оптимизировав решение.

Но настоящие алгоритмисты так не делают — они не любят зря тратить силы: писать медленные программы, измерять скорость работы и только потом думать, как ускорить решение. Вместо этого они заранее оценивают время работы алгоритма и сразу пишут эффективную программу.

В первом спринте мы расскажем о том, как подходить к решению алгоритмических задач, что такое сложность алгоритма и как правильно тестировать свою программу.Начнём с оценки эффективности. Допустим, нам нужно найти какой-нибудь элемент в массиве. Давайте рассмотрим один из возможных алгоритмов решения этой задачи и оценим время его работы.

Начнём с алгоритма поиска элемента в массиве и на его примере поговорим о том, как оценивают время работы алгоритма.

Постановка задачи:

Дан массив целых чисел длины N. Нужно найти в нём заданное число x и вернуть его индекс. Если x в массиве не встречается — вернуть -1.

Рассмотрим одно из решений этой задачи:

def find_element(numbers, x):
    for i in range(len(numbers)): # проходим по всем элементам массива
        if numbers[i] == x: # сравниваем их с иксом
            return i  # если нашли - возвращаем индекс
    return -1  # если не нашли - возвращаем -1 

Алгоритм решает поставленную задачу. Но насколько быстро он это делает?

Попробуем понять, сколько элементарных операций совершается в процессе его работы. Под элементарной операцией понимают любую арифметическую операцию или операцию сравнения.

В реализации алгоритма видно, что для каждого элемента массива будет выполнена одна элементарная операция — сравнение с x, увеличение счётчика i и т. д. Осталось понять, сколько элементов будет рассмотрено.

В зависимости от значения x будет рассмотрено разное количество элементов. Однако при оценке скорости работы алгоритма обычно оценивают сложность в худшем случае (англ. worst-case complexity).

Можем сказать, что скорость работы алгоритма в худшем случае пропорциональна размеру массива. На математическом языке ещё говорят: «Вычислительная сложность алгоритма линейно зависит от размера входных данных».

Разберём эту фразу:

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

Размер входных данных. Входные данные — то, что алгоритм получает на вход. В нашей задаче это массив numbers и переменная x. Размер входных данных примерно равен N.

Линейная зависимость. Описывается формулой y = kx + b.

Например, если в комнате xx табуретов, то количество их ножек можно посчитать по формуле y = 4x. То есть количество ножек линейно зависит от количества табуретов. Если один из табуретов оказался трёхногим, зависимость всё ещё будет линейной: y = 4x — 1.



Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: