Конспект: задача и модель стоимости

Понятия

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

Предусловие - что гарантировано про вход. Это ресурс: упорядоченность, непустота, целочисленность разрешают решать быстрее.

Постусловие - какое свойство связывает выход со входом. Именно оно проверяется, когда говорят «алгоритм верен».

Экземпляр задачи - один конкретный вход. Задача одна, экземпляров бесконечно много.

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

RAM-модель - договорённость о стоимости: арифметика, сравнение, присваивание и обращение к ячейке по номеру стоят единицу.

Что унести

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

Шагом считается операция, объём работы которой не зависит от размера данных. Всё остальное стоит столько, сколько просмотрело.

Один и тот же синтаксис стоит по-разному: x in spisok идёт по элементам, x in slovar считает адрес. В тексте программы эта разница не видна.

Набор данных подбирается под место возможного расхождения со спецификацией, а не «чтобы было побольше». Заготовка задачи главы проходила четыре набора из шести и была неверна.

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

Таблица роста читается так: данных втрое больше, шагов втрое - линия, вдевятеро - квадрат, чуть больше чем втрое - n·log n.

Ловушки джокера

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

Посчитал строки вместо работы. if x in spisok занимает два символа и стоит проход по всему списку. Лишний порядок роста почти всегда прячется за коротким синтаксисом.

Склеил строки в цикле. itog = itog + slovo создаёт новую строку каждый круг. На тысяче слов это уже квадрат. CPython дописывает на месте только локальную переменную функции, и язык этого не обещает.

Перенёс псевдокод с включённой правой границей. for i = 1 to n захватывает n, а range(1, n) - нет. Ошибка на единицу берётся отсюда чаще всего.

Проверил на двух примерах и решил, что верно. Тесты - это спецификация, записанная примерами. Примеров всегда меньше, чем случаев.

Цена операций на данных из n элементов

Проверь себя

Что не так с постусловием «выход - число, равное количеству элементов списка, больших x»?

Почему предусловие «список отсортирован» меняет достижимую сложность, а предусловие «числа целые» обычно нет?

Сколько шагов сделает for x in a: if x in b: на списках по 1000 элементов?

Чем range(1, n) отличается от for i = 1 to n и где это стреляет?