Как найти линейный алгоритм

Каждый человек на протяжении своей жизни решает множество задач разной сложности. Но даже самые простые из задач выполняются последовательно, то есть за несколько шагов. Эту последовательность можно назвать алгоритмом. Последовательности бывают разные, но начинать их изучение лучше всего с линейных.

Прежде чем приступить к рассмотрению основной темы статьи, следует сделать краткое отступление и сказать несколько слов про алгоритмический язык.

Алгоритмический язык

Представьте, что человеку, работающему за компьютером, поставлена некая вычислительная задача. В языке программирования решение этой задачи выполняется с помощью алгоритмизации. Решение предполагает:
— разбиение на этапы;
— разработку алгоритма;
— составление программы решения на алгоритмическом языке;
— ввод данных;
— отладку программы (возможны ошибки — их надо исправить);
— выполнение на ПК;
— анализ результатов.

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

Свойства алгоритма

Их несколько:
— конечность. Любой алгоритм должен быть завершённым, а окончание наступает после выполнения определённого числа шагов;
— однозначность, понятность. Не допускается разных толкований, неопределённости и двусмысленности — всё должно быть чётко и ясно, а также понятно исполнителю — и правила выполнения действий линейного алгоритма, и сами действия;
— результативность. Итог работы — результат, полученный за конечное число шагов;
— универсальность, массовость. Качественный алгоритм способен решать не одну задачу, а целый класс задач, имеющих схожую постановку/структуру.

Линейная структура

Любой алгоритм составляется из ряда базовых структур. Простейшей базовой структурой является следование — структура с линейными характеристиками. Из этого можно сформулировать определение.

Линейный алгоритм — это алгоритм, образуемый командами, которые выполняются однократно и именно в той последовательности, в которой записаны. Линейная структура, по сути, проста. Записать её можно как в текстовой, так и в графической форме.

Представим, что у нас стоит задача пропылесосить ковёр в комнате. В текстовой форме алгоритм будет следующим:
— принести пылесос к месту уборки;
— включить;
— пропылесосить;
— выключить;
— унести пылесос.

И каждый раз, когда нам надо будет пылесосить, мы будем выполнять один и тот же алгоритм.

Теперь поговорим про графическую форму представления.

Блок-схема

Для изображения алгоритма графически используют блок-схемы. Они представляют собой геометрические фигуры (блоки), соединённые стрелками. Стрелки показывают связь между этапами и последовательность их выполнения. Каждый блок сопровождается надписью.

Рассмотрим фигуры, которые используются при визуализации типичной линейной последовательности.

Блок начала-конца:

Блок ввода-вывода данных (отображает список вводимых и выводимых переменных):

Арифметический блок (отображает арифметическую операцию/группу операций):

Условный блок (позволяет описать условие). Алгоритмы с таким блоком используются при графической визуализации алгоритмов с ветвлением:

Условного блока нет в классическом линейном алгоритме, так как в нём, как уже было сказано ранее, все операции выполняются последовательно, то есть одна за другой. В линейном алгоритме размещение блоков выглядит следующим образом:

А вот, как решается задача по нахождению площади треугольника по формуле Герона. Здесь a, b, c – это длины сторон, S – площадь треугольника, P – периметр.

Следует обратить внимание, что запись «=» — это не математическое равенство, а операция присваивания. В результате этой операции переменная, стоящая слева от оператора, получает значение, которое указано справа. Значение не обязательно должно быть сразу определено (a = 3) — оно может вычисляться посредством выражения (a = b + z), где b = 1, a z = 2.

Примеры линейных алгоритмов

Если рассмотреть примеры решения на языке Pascal (именно этот язык до сих пор используется для изучения основ алгоритмизации и программирования), то можно увидеть следующую картину:

И, соответственно, блок-схема программы линейной структуры будет выглядеть следующим образом:

Как составить программу линейной структуры?

Порядок следующий:
— определите, что именно относится к исходным данными, а также каков типы/класс этих данных, выберите имена переменных;
— определите, каков тип данных будет у искомого результата, выберите название переменных (переменной);
— определите, какие математические формулы связывают результат и исходные данные;
— если требуется наличие промежуточных данных, определите класс/типы этих данных и выберите имена;
— опишите все используемые переменные;
— запишите окончательный алгоритм. Он должен включать в себя ввод данных, вычисления, вывод результатов.

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

Источники:
• https://inep.sfedu.ru/wp-content/uploads/2018/05/25/lection_27.pdf;
• https://www.sites.google.com/site/415ict/textbooks/prog-9/02-linejnyj-algoritm.

Линейный алгоритм

Линейным
называют
алгоритм,
операции и линии потоков которого идут
по одному направлению, без повторений
операций, без альтернативных путей
потоков.

Блок-схема
такого алгоритма имеет вид, представленный
на рис. 4 а.
Пример линейного алгоритма:
имеются две переменные a
и b,
произвести обмен их значениями. Блок-схема
алгоритма решения этой задачи приведена
на рис. 4 б.

Следует
отметить, что знак «=» в блоках 2, 3 и 4
означает не равенство, а операцию
присвоения переменной значения. Например,
в блоке 2 производится присвоение
переменной а суммы значений переменных
а и b.

В
блок-схеме алгоритма все операции
нумеруются (номер проставляется вверху
слева от блока) в порядке их выполнения.
Блоки «Начало» и «Конец» не нумеруются.

Ветвящийся алгоритм

Алгоритм
называется ветвящимся
(см. рис. 5),
если в нем содержится блок перехода или
условия, который имеет одну входную
линию потока и более одной выходные
линии.

Пример
ветвящегося алгоритма: найти наибольшее
значение трех переменных a,
b
и c.
Блок-схема решения этого алгоритма
приведена на рис. 6.

Рис.
5. Блок-схема ветвящегося алгоритма; а
– полное ветвление, б – непол-ное
ветвление.

Рис.
6 . Блок схема алгоритма поиска
максимального из трех значений

На рис.
7 приведен пример алгоритма вычисления
значения переменной у, определяемой
математическим выражением:

у =	f1(x) если x ≤ x1 f2(x) если x1 ≤ x ≤ x2 f3(x) если x > x2

Рис. 7. Пример
ветвящегося алгоритма

Циклический алгоритм

Алгоритм
называется циклическим,
если он содержит в своем составе
последовательность действий (операторов,
переходов), неоднократно повторяющуюся
с заданием новых начальных условий.
При этом алгоритм включает в себя
процедуры задания этих начальных
условий.

Часть
алгоритма, отражающая эти действия,
называется циклом

Как
правило, алгоритмы решения реальных
задач представляют собой комбинацию
всех трех рассмотренных типов простейших
алгоритмов. Рассмотрим алгоритмы
некоторых часто встречающиеся задач.Рис.
8. Циклический алгоритм; а – цикл «пока»,
б – цикл «до».

Алгоритмы накопления суммы и произведения

В
алгоритмах часто приходится накапливать
сумму и произведение значений функции.
Математическая запись суммы имеет вид
произведения —гдеN_n
– начальные значений переменной, N_k
– конечное значение целочисленной
переменной i.

Перед
началом процесса накопления суммы
переменной, в которой будет использоваться
сумма, необходимо присвоить значение
0. Иначе при объявлении переменной
и выделения места в памяти ЭВМ, в этом
месте может оказаться любая информация
от предыдущих операций, и мы можем
получить неверную сумму.

При
подсчете произведения переменной, в
которой будет накапливаться произведение,
необходимо присвоить начальное значение
1.

Рис.
9. Блок схемы алгоритмов накопления

а)
– суммы y
=
aⁱ
и б) — произведения y
=
sin(I*b)

Алгоритм табулирования функции

Табулирование
функции – это вычисление ее значений
по изменяющимся значениям аргумента
функции.

Табулируют
функцию, например, для построения ее
графика, для поиска ее максимальных
значений. Табулирование функции y
= f(x)
ведется на некотором интервале значений
аргумента x
€ [х_н;
х_к],
с изменением значений аргумента на
одинаковую величину ∆х, которую называют
шагом изменения х.

Пример.
Разработать алгоритм табулирования
функции y,
приведенной на стр. 44, на интервале
значений х € [х_н;
х_к],
с шагом ∆х изменения аргумента.
Блок-схема алгоритма решения этой
задачи приведена на рис. 10.

Рис.
11. Блок-схема алгоритма табулирования
функции

“Блок
1”
обеспечивает печать заголовка таблицы,
а блок 9 – строк таблицы, чтобы получить
таблицу следующего вида:

x	y
хн	yн
х + ∆х	yн+1
x + 2∆х	yн+2
…	…
хк — ∆х	yк-1
xк	yк

“Блок
2”,
“Блок
3”
и “Блок
10”
обеспечивают цикличность вычисления
y
в соответствии с изменением значения
аргумента х от начального значения х_н
до конечного значения х_к
с шагом ∆х.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Алгоритмы для веб-разработчиков простыми словами

Здравствуйте, друзья! Данным постом мы открываем цикл статей об алгоритмах и структурах данных.

В этой статье мы поговорим о том, зачем вообще их нужно знать веб-разработчикам, и затронем тему оценки сложности алгоритмов и Big O нотации.

Зачем мне алгоритмы? Я фронтендер!

Вы наверняка задумались: «А зачем мне нужно тратить своё время на изучение этих сложных алгоритмов, если я работаю с фронтендом? Как знание графов и бинарных деревьев поможет мне лучше отцентровать одну div-ку внутри другой div-ки?»

С одной стороны, знание алгоритмов и структур данных действительно напрямую не пригодится вам в практической работе. Но с другой стороны, существует одна весомая причина инвестировать немного своего времени в их изучение: знание алгоритмов и структур данных сделает вас лучше как разработчика.

Многие веб-разработчики на таких форумах, как Reddit и Stack Overflow, отмечали, что, освоив даже на базовом уровне эти фундаментальные основы программирования, чувствовали себя увереннее, профессиональнее и писали более чистый и структурированный код.

Также это помогло им прокачать главный скилл разработчика – умение логически думать и решать сложные технические задачи.

Кстати, именно по этой причине многие крупные IT-компании требуют от своих потенциальных сотрудников знания фундаментальных основ computer science, к которым как раз относятся алгоримты и структуры данных, и с пристрастием спрашивают их на собеседованиях (даже на позицию фронтенд-разработчика!).

Ведь они ищут лучших из лучших, и знание алгоритмов как раз делает вас лучше как разработчика. Тем более, лучше инвестировать свое свободное время в новые знания и навыки, чем в сериалы на Netflix.

И на этой прекрасной ноте давайте перейдем к основной теме статьи.

Что такое алгоритмы и структуры данных

Алгоритм — это совокупность последовательных операций, направленных на решение определенной задачи.

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

Эта запись имеет вид O(n), где n – это количество операций, которое предстоит выполнить алгоритму. Важное замечание: O(n) всегда описывает худший возможный случай выполнения алгоритма. Это дает нам гарантию, что наш алгоритм никогда не будет работать медленнее O(n).

Скорость работы алгоритмов измеряется не в секундах, а в темпе роста количества операций. Т.е. нас интересует, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.

Вот так выглядит время работы некоторых алгоритмов:

O(1) – константное время. Например, чтение данных из ячейки в массиве.

O(log n) – логарифмическое время. Например, бинарный поиск.

O(n) – линейное время. Например, поиск наименьшего или наибольшего элемента в неотсортированном массиве.

O(n * log n) – линейно-логарифмическое время. Например, быстрая сортировка.

O(n2) – квадратичное время. Например, сортировка пузырьком.

O(n!) – факториальное время. Например, решение задачи коммивояжера полным перебором.

Алгоритм линейного поиска

Давайте для начала рассмотрим такой простейший алгоритм, как линейный поиск элемента в массиве, и реализуем его на JavaScript.

Итак, есть массив чисел, и нам нужно найти в нем конкретное число.

Создадим функцию линейного поиска и назовем ее linearSearch. Эта функция будет принимать в себя два параметра: array (т.е. сам массив элементов, в котором ведется поиск) и item (элемент, который мы ищем в этом массиве).

Линейный поиск происходит достаточно предсказуемо: мы используем цикл for, в котором пробегаемся по элементам массива и сравниваем каждый элемент с искомым.

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

 let i = 0;

Наш цикл будет выполняться до тех пор, пока не пройдет по всем элементам массива. В качестве конечной точки мы используем значение array.length, которое возвращает количество элементов в массиве. Так как массив array начинается с нулевого индекса, то мы используем при сравнении знак «<».

i < array.length;

После каждой итерации цикла увеличиваем значение переменной i на единицу.

i++

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

Здесь мы сравниваем каждый элемент массива (array[i]) c искомым элементом (item) и, если эти элементы совпадают, то возвращаем i (индекс массива, по которому находится этот искомый элемент item).

Если же искомый элемент не был найден, то по завершении работы цикла мы возвращаем -1.

Дальше нам остается только вызвать функцию linearSearch, первым параметром передать в нее массив элементов, а вторым параметром — искомое число.

Затем, с помощью функции console.log, выводим результат в консоль.

Продублируем код для копирования:

const array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function linearSearch(array, item) {

  for (let i = 0; i < array.length; i++) {

    if (array[i] === item) {

      return i;

    }

  }

  return -1;

}

console.log(linearSearch(array, 5)); // Вызываем функцию и получаем 5.

Как видите, алгоритм линейного поиска довольно прост в реализации. Сложность данного алгоритма: линейное время или O(n).

Давайте теперь рассмотрим более сложный и интересный алгоритм, который еще называют алгоритмом бинарного поиска.

Алгоритм бинарного поиска

Бинарный (или двоичный) поиск — это алгоритм, при котором массив данных будет последовательно делиться пополам до тех пор, пока не будет обнаружен искомый элемент.

Важное замечание: данный алгоритм будет работать только для отсортированного массива.

Бинарный поиск может быть реализован следующим образом:

0. Берём исходный массив отсортированных данных (например, по возрастанию).

1. Делим его на две части и находим середину.

2. Сравниваем элемент в середине с искомым элементом.

3. Если искомое число меньше этого центрального элемента — продолжаем искать элемент в левой части массива. Для этого мы делим левую часть массива на 2 части. Если искомый элемент больше центрального элемента, то мы отбрасываем левую часть массива и продолжаем поиск в правой.

И повторяем данную процедуру до тех пор, пока не найдем искомый элемент. Как только мы его нашли, то возвращаем индекс в массиве, по которому он находится. Если же данный элемент не будет найден, то возвращаем -1.

Давайте сначала взглянем на реализацию данного алгоритма, а потом разберем ее детально.

const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

const binarySearch = (arr, value) => {

  let start = 0;

  let end = arr.length - 1;

  while (start <= end) {

    let middle = Math.floor((start + end) / 2);

    if (value === arr[middle] ) return middle;

    if (value < arr[middle]) {

      end = middle - 1;

    } else {

      start = middle + 1;

    }

  }

  return -1;

};

console.log(binarySearch(arr, 5)); // 5

Итак, у нас есть массив чисел arr, отсортированный по возрастанию. Как вы помните, если заранее не отсортировать массив, то бинарный поиск не будет работать.

Создаем функцию binarySearch и передаем в нее два параметра: отсортированный массив arr и искомый элемент value.

Затем определяем следующие переменные:

let start = 0;

Так как мы должны найти центральный элемент, то сначала необходимо определить начальный и конечный элементы.

Задаем таким образом начальный элемент и устанавливаем его значение равным нулю, так как наш массив начинается с нулевого индекса.

let end = arr.length - 1;

Затем определяем конечный элемент. Его позиция будет вычисляться по длине массива arr.length - 1.

Далее мы создадим цикл while, который будет работать до тех пор, пока начальная и конечная позиция массива не сравняются (start <= end).

let middle;

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

Результат обернем в функцию Math.floor(), так как в результате деления у нас может получиться дробное число. С помощью данной функции мы округляем полученное число до нижней границы.

Далее с помощью условной конструкции if создаем проверку: если центральный элемент в массиве по индексу middle равен искомому элементу, то мы возвращаем индекс найденного элемента, сохраненный в переменной middle. И на этом наша функция завершает свою работу.

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

Для этого нам нужно изменить значение переменной end. В итоге мы получим end = middle + 1. А в блоке else мы прописываем такое же условие, только для случая, если искомый элемент будет больше, чем элемент, находящийся в середине. Тогда мы отбрасываем левую часть массива и продолжаем поиск в правой.

После завершения цикла while возвращаем -1 на случай, если искомое число не будет найдено в массиве. Далее вызываем функцию binarySearch и передаем в нее два параметра: массив элементов и искомое число.

И выводим результат в консоль.

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

Последовательная сложность бинарного поиска в худшем и среднем случаях равна O(log n), в лучшем — O(1) (если обнаруживаем искомый элемент на первой итерации). Для сравнения: вычислительная сложность линейного поиска, как вы помните, равна O(n).

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