Проблемы реализации
Когда мы работаем с алгоритмами и структурами данных, порой возникает искажённое впечатление, будто это что-то чрезвычайно сложное. Однако в большинстве случаев они просты и интуитивно понятны. Нужно лишь немного попрактиковаться и поработать руками, чтобы лучше почувствовать, как эти алгоритмы действительно работают.
При рассмотрении конкретных задач и упражнений вскоре становится очевидно, что некоторые группы и категории задач можно объединить. Они обладают общими характеристиками, позволяющими применять единые подходы чтo касается каждой группы.
Один из таких типов – это задачи на реализацию. В таких задачах чаще всего шаги решения уже описаны прямо в условии. То есть в самом задании изложено, какие действия программа должна выполнить. Задача инженера-программиста заключается в том, чтобы эффективно воплотить эти шаги и получить желаемый результат. Важно понимать, что, даже если нужные шаги перечислены в задаче, их реализация может быть не такой уж и очевидной.
Задача – найти пропущенное число
Даны все числа от 1 до
n, кроме одного. Нужно найти это пропущенное число.Input
Первая строка входных данных содержит одно целое число
n (2 ≤ n ≤ 100 000).Вторая строка содержит
n-1 целых чисел, разделённых пробелами, (1 ≤ ≤ n).Output
Программа должна вывести пропущенное число.
Примеры
Input | Output |
4
3 4 1 | 2 |
3
2 1 | 3 |
Разбор сложности и нотации Big
Даже если описанная выше задача кажется простой, наивное решение может оказаться слишком медленным для всех тестовых случаев.
Наивный подход может заключаться в том, чтобы считать все элементы из входных данных в список, а затем пройти по всем числам от
1...n и проверить, содержится ли каждое число в этом списке. Если число отсутствует в списке – это и есть наш ответ:n = int(input())
a = [int(ai) for ai in input().split()]
for i in range(1, n + 1): # n операций
if i not in a: # n операций (проход по всем элементам)
print(i) # Решение найдено!Такой алгоритм на самом деле очень медленный. Он перебирает все числа
1...n и для каждого проверяет, есть ли оно в списке. Проверка «число присутствует в списке» – это линейная операция, поскольку программа последовательно проходит все элементы a и сверяется, совпадает ли текущий элемент со значением i. Поэтому для проверки присутствия i в списке требуется n операций, ведь длина списка примерно n (точнее n-1, но на порядок это не влияет).Итоговое число операций получается порядка . Внешний цикл выполняется
n раз, а проверка в списке тоже занимает n операций. Значит, всего получится примерно операций (в худшем случае).💻
Наши компьютеры могут выполнять примерно 10–100 миллионов операций в секунду. Если ограничение по времени на задачу – 1 секунда (а это стандартный лимит для алгоритмических задач), нам нужно стремиться к тому, чтобы общее число операций не превышало 100 миллионов.
В задаче выше число
n может достигать 100 000, следовательно, алгоритм выполнит около операций, то есть 10 миллиардов. На обычном компьютере это займет примерно 100 секунд, а лимит времени – всего 1 секунда. Нужно найти более оптимальное решение.Нотация Big
Нотация Big O – это математический инструмент, позволяющий описать верхнюю границу скорости роста времени работы алгоритма при увеличении размера входных данных. Она даёт приблизительную оценку того, сколько операций потребуется алгоритму в зависимости от объёма входной информации.
Для описанного решения мы оценили, что алгоритм выполняет порядка операций в сумме. Следовательно, по сложности это можно записать как .
Мы обсудим это более детально и формально позже в курсе, предложив дополнительную интуицию и примеры.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB