Алгоритмы для жизни: Простые способы принимать верные решения (Гриффитс, Кристиан) - страница 54

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

Это самая простая категория задач, которая называется «О большое от единицы» (обозначается как «О(1)») и также известна как временнáя константа. Примечательно, что для «О большого» абсолютно не важно, сколько времени у вас на самом деле занимает уборка. Главное – что временной промежуток всегда один и тот же, вне зависимости от списка гостей. От вас требуется выполнить одну и ту же работу, не важно, пригласили вы одного друга, десять, сто или любое другое количество.

Теперь время, которое займет передача жаркого вокруг стола, мы обозначим как «О большое от n» (письменно – «O(n)»). Это понятие также имеет другое название – «линейное время». Если количество гостей увеличивается в два раза, то же происходит и с линейным временем. И снова, для «О большого» безразлично, какое количество блюд вы подаете или, например, сколько раз гости попросят добавки. В каждом случае время линейно зависит от количества приглашенных гостей и график зависимости времени от количества гостей будет представлять собой прямую. Более того, существование любых линейно-временных факторов – в случае «О большого» – будет перекрывать все факторы временных констант.

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

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

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

Эта задача перейдет уже в разряд «О большое от n в квадрате» («О(n2)»), или квадратичного времени. Опять же для нас важны только общие черты связей между переменной n и временем. Не существует формулы O(2n2) для двух объятий на каждого или формулы O(n2 + n) для объятий и передачи блюда. Таким образом, O(n2) охватывает все процессы.

Вот здесь становится трудно, потому что появляется экспоненциальное время, которое рассчитывается по формуле O(2n), когда каждый дополнительный гость удваивает вашу работу. Еще сложней все обстоит с факториальным временем, определяемым по формуле O(