Если вы когда-либо застревали на том, какой метод использовать для решения проблемы, размышление о сложности — лучшая отправная точка. Простой способ выразить сложность — использовать нотацию Big O.
Что такое нотация Big O?
Короче говоря, нотация Big O алгебраически описывает, насколько сложна программа. Это определение довольно расплывчато, поэтому обычно его объясняют на примере, таком как O(log(n)). Здесь n представляет количество входных данных, которые будет принимать ваша программа, а функция «log(n)» представляет сложность алгоритма по отношению к размеру входных данных.
Чтобы найти сложность нотации Big O вашего кода, посчитайте операции. Когда ваша программа зациклится на коде, добавьте n операций. Не забудьте умножить количество операций в цикле на количество запусков цикла. Вот пример на Python:
Если x является нашим входом, то сложность этого будет 2+n. Однако мы можем удалить любые константы с помощью Big O Notation, поэтому сложность этого кода будет O (n). Это означает, что сложность функции будет масштабироваться линейно с размером входных данных. Если ввод становится в два раза больше, программа становится в два раза сложнее, и ее выполнение должно занимать примерно в два раза больше времени.
Как это связано с конкурентным кодированием?
Допустим, вы рассматриваете метод со встроенным циклом:
Если вы хотите быстро оценить, сработает ли этот подход в рамках временных ограничений вашей проблемы, подумайте о сложности. Поскольку имеется встроенный цикл, сложность нотации Big O будет равна O(n²). Хотя это отлично работает для нашего размера ввода 5, это означает, что сложность будет масштабироваться квадратично с размером ввода. Если бы у нас было 10000 строк ввода (не редкость в соревнованиях по кодированию), наша сложность была бы огромной.
Хотя эта программа очень проста, и ее простое написание и запуск не займет много времени, более сложные проблемы потребуют гораздо более сложных решений, которые требуют значительно больше времени для отладки и тестирования. Проверяя сложность с помощью нотации Big O, вы можете быстро оценить, будет ли работать ваш подход, не тратя усилий и времени на создание и тестирование самой программы. Короче говоря, вы можете оценить, сколько времени займет выполнение вашей программы, фактически не запуская ее.
Общие сложности в нотации Big O
При тестировании различных алгоритмов вы заметите, что сталкиваетесь с несколькими очень распространенными сложностями O. Вы можете увидеть, как быстро сложность масштабируется в зависимости от ввода, на следующей диаграмме:
Как вы можете видеть, все, что выше O(n), будет довольно плохим при запуске с большим размером входных данных. На соревнованиях по программированию я редко видел функционирующее решение со сложностью выше O(nlog(n)), и обычно это были последние несколько задач.
Однако есть одна ситуация, когда вы должны использовать программу со сложностью O (n²), и это если у вас мало времени, а это простое решение. Часто легко написать простую, но менее эффективную программу, которая даст вам частичные оценки за задачу. Если у вас почти не осталось времени, часто лучше перестраховаться, сократить свои потери и выбрать плохое, но простое решение. Конечно, если вы практикуетесь, всегда старайтесь найти самый эффективный; этот совет применим только во время соревнований, чтобы максимизировать очки.
И это краткий обзор нотации и сложности Big O! Я надеюсь, что этот совет пригодится вам в вашем следующем соревновании по программированию. Если вам понравилась эта статья, вы можете найти мой сайт здесь и мой LinkedIn здесь.
