Одна вещь, которая постепенно становится очень важной, чем дольше вы разрабатываете, - это временная сложность, она может быть сложной на первый взгляд, но постепенно станет проще, чем больше вы будете использовать ее, как и все остальное. Я провел много времени, читая множество статей, просматривая тонны видео, чтобы полностью понять цель этой формулы. Мое намерение состоит в том, чтобы максимально упростить эту концепцию для тех, кто вроде меня, где потребовалось некоторое время, чтобы ее щелкнуть.
Так что же такое временная сложность? Проще говоря, это анализ, который мы используем в программировании, чтобы рассчитать, сколько времени требуется для запуска алгоритма с числом входных данных (n), а также сколько времени требуется для выполнения задачи, в которой используются входные данные. Распространенное неправильное название , как показано выше, представляет собой нотацию Big-O. Big O на самом деле представляет собой набор общих временных сложностей и определений.
O(1)
Обычно рассматривается как наиболее эффективный рядом друг с другом анализ. В этой формуле для выполнения задачи требуется один шаг. Это называется постоянным временем. Идея состоит в том, что он всегда будет иметь одинаковое время выполнения. Примером может быть доступ к значению в индексе массива или сколько минут потребуется, чтобы начать новый час.
O(n)
Этот алгоритм называется линейным временем. Идея здесь в том, что время выполнения пропорционально размеру ввода (n). Хорошим примером здесь может быть поиск шоу для просмотра на Netflix, где размер библиотеки для приложения постоянно меняется.
O(n²)
Логарифмическое время может сначала немного сбивать с толку, но на базовом уровне этот алгоритм пропорционален логарифму входного размера (n). Логарифм — это известное количество, которое потребуется для фиксированного числа (по основанию), чтобы произвести желаемое число. Подобно тому старому рекламному ролику «сколько нужно лизать, чтобы попасть в центр тутси-попа?» Примером для программиста может быть бинарный поиск, поскольку он часто используется для поиска в больших наборах данных.
O(n^²)
Квадратичное время, как его часто называют, похоже на логарифмическое в том смысле, что оно пропорционально квадрату входного размера (n). Этот алгоритм довольно распространен при работе с вложенными итерациями. Такие как вложенные циклы for циклы, и они могут быть еще глубже, иногда доходя до O(n^³), O(n^⁴) и т. д. Один пример, который я всегда использую здесь подсчитывает дубликаты в колоде карт. Что касается примеров разработчиков, популярными реализациями являются пузырьковая сортировка. сортировка выбором и сортировка вставками.
Вывод
Завершение этого должно было сделать эти алгоритмы как можно более простыми и разбить основы для каждого анализа сложности. На самом деле это лишь малая часть того, что они способны вычислить, но дает отличную основу для понимания концепции.
