Одна проблема, чтобы покрыть все сложности времени

Question

Преподаватель колледжа здесь. Я пытаюсь найти содержательный (практический) пример кода, чтобы проиллюстрировать различные временные сложности для начинающих в стиле ELi5. Код должен начинаться с постоянной сложности, а затем постепенно, добавляя небольшой фрагмент кода, усложняется: .., logn, n, nlogn, n ^ 2, 2 ^ n, ..

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

Answer 1

Любой пример будет искусственным. Но вот тот, который работает достаточно хорошо.

Пусть vec будет отсортированным массивом чисел, i целое число, а x будет другим числом. Для того, чтобы ответить на следующие вопросы:

1. O(1) Какое значение vec[i]?
2. O(n) Is x в диапазоне от vec по линейному поиск?
3. O(log(n)) Является ли x в диапазоне от vec бинарным поиском?
4. O(n^2) Является ли x суммой двух элементов в диапазоне от vec двойным l oop?
5. O(n log(n)) Является ли x суммой двух элементов vec при линейном поиске по первому с двоичным поиском по второму. (Упростая трюк, выполните линейный поиск по младшему и двоичному по второму. Затем повторно используйте ваш код из 3.)
6. O(2^n) Является ли x суммой любого подмножества элементов vec по рекурсия?
7. (псевдополином). Помните предыдущее решение. Обсудить соотношение памяти и скорости.