Как работает сложность времени и пространства?

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

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

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

Согласно Wikipedia определение временной сложности: В« информатике временная сложность - это вычислительная сложность , которая описывает количество времени, которое требуется для выполнения алгоритма . ”

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

  • Таким образом, считается, что количество затраченного времени и количество элементарных операций, выполняемых алгоритмом, различаются не более чем на постоянный коэффициент.
  • Резюмируя выше, временная сложность определяет количество шагов, необходимых для запуска алгоритма.
  • Сложность пространства определяет объем памяти, необходимый для программы в системе или компьютере. Сложность времени в худшем случае проверяется путем сравнения двух алгоритмов.

Рассмотрим пример приготовления чая. На этом этапе добавления сахара будут следующие этапы.

Алгоритмические шаги, необходимые для вышеуказанного сценария:

1) Принесите миску с сахаром.

2) Возьмите ложку.

3) Вычерпайте ложкой сахар.

4) Насыпьте сахар из ложки в чай.

5) Повторяйте шаги 3 и 4, пока не добавите желаемый сахар.

Таким образом, временная сложность будет обозначаться нотацией Big O. Для нашей задачи с сахаром у нас будет следующая нотация с большим o:

  1. Количество желаемых сахаров = n.
  2. Общее количество шагов = 2n + 2.
  3. С ростом n количество шагов растет.

2 в «2n» и «+2» остаются постоянными, поэтому они не играют никакой роли во временной сложности. Значение n определяет временную сложность.

  • Сложность времени составит O (n).
  • Это будет линейная временная сложность.

Вот некоторые из типов нотации Big O:

  1. O (1): константа и наилучшая временная сложность для достижения.
  2. O (logn): это логарифмическая временная сложность.
  3. O (n): это линейная временная сложность.
  4. O (nlogn): это n log-star n.
  5. O (n²): квадратичный и худшая временная сложность для достижения.

Общая пошаговая процедура анализа времени выполнения Big-O выглядит следующим образом:

  1. Выясните, что это за ввод и что представляет собой n (желаемое количество сахарных ложек было n в нашем примере выше).
  2. Выразите максимальное количество операций, выполняемых алгоритмом, через n.
  3. Исключить все, за исключением условий наивысшего порядка.
  4. Удалите все постоянные факторы.

Алгоритмические примеры анализа времени выполнения:

Некоторые из примеров всех этих типов алгоритмов (в наихудших сценариях) упомянуты ниже:

▪ Логарифмический алгоритм - O (logn) - двоичный поиск.

▪ Линейный алгоритм - O (n) - линейный поиск .

▪ Суперлинейный алгоритм - O (nlogn) - Сортировка кучи, сортировка слиянием.

▪ Полиномиальный алгоритм - O (n ^ c) - умножение матриц Штрассена, пузырьковая сортировка, сортировка по выбору, сортировка вставкой, сортировка по сегментам.

▪ Экспоненциальный алгоритм - O (c ^ n) - Ханойская башня.

▪ Факториальный алгоритм - O (n!) - Детерминантное расширение по несовершеннолетним, алгоритм поиска грубой силы для задачи коммивояжера.

Математические примеры анализа времени выполнения:

Производительность (время выполнения) алгоритмов разных порядков быстро различается по мере увеличения n (входного размера). Рассмотрим математический пример:

If n = 10,

журнал (10) = 1;

10 = 10;

10log (10) = 10;

102=100;

210=1024;

10!=3628800;

If n = 20,

журнал (20) = 2,996;

20 = 20;

20log (20) = 59,9;

202=400;

220=1048576;

20!=2.432902e+1818;

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

Кредиты: www.geeksforgeeks.com

Кредиты: https://en.wikipedia.org/wiki/Time_complexity