Эта история начнется в поликлинике, где предстоит диспансеризация работников образования. Сегодня в ней ожидается наплыв большого количества посетителей.
- Дорогие коллеги, впереди трудный день. Но нам нужно работать продуктивно и успеть принять всех посетителей за отведенное время, - сказал директор.
- Во сколько сегодня освободимся? А то у меня свидание назначено на пять часов, - сказал доктор Сергеев.
- Точно сказать не могу. Нужно проанализировать. Для этого возьмём самый худший вариант, к примеру 150 человек за сегодня должно нас посетить. Отсюда, будем рассчитывать максимальное время выполнения нашейработы, - ответил директор. ---------------------------------------------
На этом я остановлю рассказ и поясню, что происходит.
Переведем информацию на язык программирования. Поликлиника - это имя переменной, в которой будет хранится массив. Массив - это посетители. По заявлению директора, максимальное количество посетителей сегодня - 150 человек, значит это последний элемент в массиве.
---------------------------------------------
Продолжение...
Директор листает тетрадку, водит по ней пальцем:
- О, Сергеев, у тебя сегодня выезд и осмотр специалистов в организации. Я думаю на свидание ты успеешь. В этом учреждении всего 15 человек. Учитывая нашу норму - 10 минут на человека. Считай сам, но к пяти ты точно будешь свободен.
- Если я здесь не нужен, может я уже поеду?
- Да, иди. Список сотрудником получишь у заведующей.
Когда Сергеев приехал в организацию, то у заведующей он получил два списка. Один содержал список всех сотрудников, другой - время, когда тот или иной сотрудник свободен.
- Как обычно, всё не так как ожидалось. Ладно, разберемся и с этим. Кто у нас сейчас свободен, - водит пальцем по списку времени. - О! Вызовите мне на осмотр Колмакова, сейчас у него нет урока, затем Азарова, потом Белоусова и ... --------------------------------------------
Пояснение.
У Сергеева в организации заявлено 15 человек. Количество людей заранее известно. Значит легко можно рассчитать время его работы. По норме на одного человека выделяется 10 минут. Значит на 15 человек Сергеев потратит 150 минут. Это время называется константное, потому что 15 человек в любой другой организации, также пройдут обследование за 150 минут.
Записывается так:
1) О(1) - константное время - выполнение алгоритма за одинаковое количество времени.
примеры:
- доступ к элементу массива по индексу,
- вывод массив на печать
--------------------------------------------
Продолжение...
В поликлинике появились первые посетители. Началась работа. Люди одни за другим заходили в кабинет Хирурга и через десять минут выходили.
Ко двору здания подъехали два автобуса. Из них вышли организованные группы людей с бейджиками на форме. Они быстро выстроились в ряд и дружно зашли в здание. Стоит заметить, что одна группа была в форме красного цвета, другая в синей. Оказалось, это прибыли сотрудники детской школы Счастья из Заводского и Кировского района. --------------------------------------------
Пояснение.
Люди идут в кабинет друг за другом. Если представить, что мы их поставили линию, то получим название линейное время.
2) O(n) - линейное время - выполнение алгоритма с перебором всех элементов (проход от начала массива до конца).
Чем больше массив, тем дольше по времени работает алгоритм. Представим себе, что вчера поликлиника обслужила 46 человек, а сегодня предполагается 150 человек. Значит сегодня придется работать дольше, чем вчера. Но что будет завтра?
В программировании проход по массиву осуществляется с помощью одного цикла, таких как for, while и т.д.
пример:
- умножить все элементы массива на два,
- все первые буквы в массиве сделать заглавными,
- нахождение максимального / минимального значения в массиве.
Теперь рассмотрим случай прибытия на обследования двух групп людей. Объединенных в одну общую группу. Это тоже будет линейное время. Только два массива складываются.
Записывается это так:
О(n+m) - объединение двух отсортированных списков в общий отсортированный список.
Теперь время зависит от суммы размеров входных данных.
----------------------------------------------
Продолжение...
Когда в поликлинике стало много посетителей, за дело взялась медсестра Тамара Ивановна. Теперь, после регистрации, первые пять человек были направлены в коридор Диагностики и лабораторного обследования, где они проходили УЗИ, ЭКГ, флюорографию, сдавали ПЦР, общий анализ крови и т.д.
----------------------------------------------
Пояснение.
В данном случае у нас массив состоит из 5 человек, которые проходят по кабинетам. Но, кабинеты - это тоже массив. Чтобы все люди прошли по всем кабинетам, должен получиться вложенный цикл ( for внутри for).
Время работы этого алгоритма записывается так:
3) О(n^2) - квадратичное время - выполнение алгоритма имеет сложность порядка n квадрат (это когда каждый элемент первого списка обрабатывается с каждым элементом второго списка).
Тут стоит вспомнить линейное время, которое записывалось как O(n) и имело один цикл. Когда добавляется второй цикл, то получаем O(n*n = n^2).
примеры:
- сортировка пузырьком,
- сортировка вставками,
- алгоритмы сравнения элементов в массивах.
----------------------------------------------
Продолжение...
Директор проходит мимо стойки регистрации и замечает как Тамара Ивановна судорожно листает телефонную книгу. Она уже готова растерзать её.
- Тамара Ивановна, что с вами?
- Никак не могу в этой книге найти нужную фамилию.
- А как вы это делает?
- Как все. Листаю, ищу букву.
- Тамара Ивановна, давайте я вас научу как надо искать. Какую фамилию ищите?
- Маркова
- Открываете книгу где-то посередине и смотрите, какая вверху буква. У нас это буква К, но мы же с вами ищем букву М. Делаем вывод, буква М идет после К, значит первая половина книги нам не нужна, мы не тратим на неё время. Теперь находим середину второй половины книги и открываем. Смотрим букву, это П.
- Да вы ж перескочили!
- Правильно заметили. Но, половина, которая у меня в правой руке, теперь нам не нужна, потому что там будут буквы Р, С, Т и так далее. Я беру те страницы, что в левой руке и опять открываю приблизительно по середине. О! Смотрите, буква М нашлась. Дальше фамилию найдете сами.
- Какой вы умный, Павел Анатольевич! Вы так быстро справились. Спасибо вам огромное.
- Да не за что.
Павел Анатольевич мило улыбнулся и спокойно удалился в свой кабинет.
--------------------------------------------
Пояснение.
В данной истории в качестве массива представлена телефонная книга. Она содержит набор букв, которые упорядочены в соответствии с алфавитом. Другими словами, мы имеем упорядоченный массив, в котором легко производить поиск, если знать алфавит.
Время работы этого алгоритма записывается так:
4) O(log n) - логарифмическое время - выполнение алгоритма с отсечением части в упорядоченном массиве.
Еще раз повторю, что здесь все алгоритмы, где происходит деление пополам или отсечение части массива, до тех пор пока не найден необходимый элемент.
пример:
- бинарный поиск
----------------------------------------- Продолжение...
Наступил вечер. Посетители все разошлись. Павел Анатольевич собрал сотрудников в холле.
- Дорогие мои коллеги, вы сегодня все молодцы. Замечательно потрудились. Сегодня нас посетило 73 человека. Мы ожидали большего количества людей - 150 человек, но не все смогли прийти. Благодарю вас всех за работу. А теперь пора по домам. Встретимся завтра.
Все дружно похлопали и помаленьку стали двигаться к выходу, прощаясь друг с другом.
------------------------------------------
В качестве заключения опишем еще одну запись:
5) О(2^n) - экспоненциальное время - выполнение алгоритма с использованием рекурсии путем разделения основной задачи на подзадачи.
Таким образом, чем больше входных данных поступит, тем дольше будет работать алгоритм.
