Мои три совета по изучению нотации Big O.

Нотация Big O – это просто пугающий способ сказать “анализ времени выполнения”. Для любого, кто когда-либо программировал, идея анализа времени выполнения не так уж удивительна. В ней есть интуитивный компонент. Когда вы пишете код, вы хотите понять, насколько сложным он будет или насколько удручающе медленным он может быть. В этом контексте Big O – это способ описания наихудшего случая такого анализа. Рассматривая часть кода, вы используете Big O для описания наихудшего случая сложности кода. Существует множество причуд, которые могут проявиться при назначении нотации Big O для данного фрагмента кода, но я хотел бы поделиться некоторыми советами, которые помогли мне освоить эту концепцию.

Совет 1: Поймите входные данные

Всегда начинайте с размышлений о характере входных данных. Будучи программистом-самоучкой и интуитивным программистом, я часто не задумываюсь о природе или сложности входных данных; это может показаться само собой разумеющимся. Однако входные данные определяют сложность кода во время выполнения.

При анализе или написании кода подумайте, что является входными данными и какие операции вы выполняете. Является ли входной информацией список или словарь? Входит ли вход в цикл for? Одинаков ли входной сигнал для обеих частей цикла? Подумайте критически о характере входных данных.

Совет 2: Пройдитесь по коду

Часто я испытываю искушение посмотреть на кусок кода как на единый блок и просто сказать: “Вот что это делает”. Это не очень хорошо подходит для анализа Big O, где могут быть тонкие морщинки, которые меняют сложность операции.

Вместо того чтобы думать о коде как о блоке, я теперь стараюсь рассматривать его как набор операций над входными данными. Чтобы действительно сделать это на тактическом уровне, я предлагаю пройтись по коду строка за строкой, подобно тому, как это делается с помощью отладчика. В каждой строке уточните, что является входом и какие операции в этой строке делают для получения выхода. При этом вы увидите, какие операции увеличивают сложность, а какими можно пренебречь. Вы избежите ситуации, когда, двигаясь слишком быстро, упускаете из виду скрытую сложность.

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