Page 276 - Bkhargava_-_Grokaem_algoritmy

Глава 2 275

Ответ: О(п). Возможно, кто-то подумает: «Я делаю это только для
одной из 26 букв, а значит, время выполнения должно быть равно
О(п/26).» Запомните простое правило: в «О-большое» игнорируются
числа, задействованные в операциях сложения, вычитания, умно­
жения или деления. Ни одно из следующих значений не является
правильной записью «О-большое»: О(п + 26), О(п - 26), О(п * 26),
О(п / 26). Все они эквивалентны О(п)! Почему? Если вам интересно,
найдите раздел «Снова об "О-большом"» в главе 4 и прочитайте о кон­
стантах в этой записи (константа - это просто число; в этом вопросе
26 является константой).

Глава 2

2.1 Допустим, вы строите приложение для управления финансами.

1. n РО..П.УКТЫ

2. кино
3. ЬЕЛОСИПЕ..а.НЫ~
КЛУБ

Ежедневно вы записываете все свои траты. В конце месяца вы анали­
зируете расходы и вычисляете, сколько денег было потрачено. При
работе с данными выполняется множество операций вставки и отно­
сительно немного операций чтения. Какую структуру использовать -
массив или список?

Ответ: В данном случае траты добавляются в список ежедневно,
а чтение всех данных происходит один раз в месяц. Для массивов
характерно быстрое чтение и медленная вставка, а для связанных
списков - медленное чтение и быстрая вставка. Так как вставка будет
выполняться намного чаще, чем чтение, есть смысл воспользоваться
связанным списком. Кроме того, чтение в связанных списках происхо­
дит медленно только при обращении к случайным элементам списка.
Так как читаться будут все элементы списка, связанный список также
неплохо справится с чтением. Итак, связанный список станет хорошим
решением этой задачи.

www.trk.kg