Виды циклов

В программировании существует два вида циклов – это потенциально бесконечные и конечные циклы.

Цикл while

Цикл while по своей структуре очень похож на if. Чтобы сделать какое-то действие вам необходимо, чтобы сначала выполнилось условие. Если условие не выполняется, то и действие тоже не будет выполнено.

Главная разница в том, что if проверяет условие только один раз. while работает так: до тех пор, пока условие выполняется, будет выполняться тело цикла (иными словами, пока результат условия - True)

Завершение цикла

Интересный момент, о котором забывают разработчики. Так как while имеет много общего с if (я делаю на этом особый акцент, так как существуют языки, где бывает так, что цикл будет выполняться, пока условие НЕ выполняется), разработчики добавили возможность использовать else поле цикла.

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

Особенностью является то, что else плохо дружит с break: если цикл завершился не тем, что условие цикла вернуло False, а прерыванием через break, то else выполняться не будет.

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

Временная сложность

Немного остановимся на этом пункте, поскольку понимание временной сложности очень важно для программиста.

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

О-нотация

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

Помните пример про официанта? Его О-нотация будет иметь вид O(n*m), где n – это количество итераций внешних циклов(обход столов), а m – это количество итераций внутренних циклов (то есть тарелок).

Для чуть большего понимания: обычный линейный код имеет сложность О(1), так как на каждую строку приходится 1 операция. Такую сложность называют константной. Она так называется, потому что независимо от количества введенных данных выполняется фиксированное количество операций. Например:

print("hello!")

Если при этом вы захотите запустить цикл на 10 кругов, то его сложность будет О(10), но если вы не знаете, сколько будет кругов цикла, то пишут О(n). Такую сложность называют линейной, так как количество операций линейно зависит от входных данных (сколько операций напишете - столько и будет).

n = int(input("Сколько кругов цикла? "))
i = 0
while i < n:
i += 1

Ну а вложенные уже имеют как раз сложность О(n*m)

n = int(input("Сколько кругов цикла 1? "))
m = int(input("Сколько кругов цикла 2? "))
i_n = 0
while i_n < n:
i_n += 1

i_m = 0

while i_m < m:

i_m += 1

При этом если m == n, то такая сложность будет квадратичной и будет иметь нотацию O(n^2). 

Про задачу на поиск числа

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

Как в этом случае посчитать количество шагов? Каждый раз мы сокращаем диапазон для поиска в два раза, а среднее количество попыток равно 3. И тут-то мы подключаем математику (это будет сложно!) и замечаем, что:

Для диапазона в 100 чисел попыток будет в среднем 6-7
Для диапазона в 1000 чисел попыток будет в среднем 9-10

И так далее. Такой прирост полностью описывает логарифмическая функция, log(2)n (читается как логарифм n по основанию 2), где n –  это начальное количество чисел. 

Соответственно сложность поиска числа по такому алгоритму будет логарифмической, и соответствовать нотации О(ln n) (натуральный логарифм по числу n). Внимание! Это общая запись сложности алгоритмов, которые используют логарифм, если говорят про конкретную формулу, то будут писать полностью.

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

Вывод

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

Вообще весь этот алгоритм поиска, где вам нужно делить пополам, описывает алгоритм бинарного поиска, который очень часто помогает в поиске элементов в массиве. Но до этого мы еще дойдем.