Что такое логарифмическая временная сложность? Полное руководство

Что такое логарифм ?

The power to which a base needs to be raised to reach a given number is called the logarithm of that number for the respective base.
For finding logarithmic two necessary factors that need to be known are base and number. 

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

Что понимается под анализом сложности?

Основным мотивом использования DSA является эффективное и действенное решение проблемы. Как определить, эффективна написанная вами программа или нет? Это измеряется сложностью. Сложность бывает двух видов:

Что такое космическая сложность?

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

Что такое временная сложность?

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

Есть три случая, обозначаемые тремя разными обозначениями анализа:

• Обозначение Big-oh(O) : обозначает верхнюю границу времени выполнения любого алгоритма, т. е. время, затрачиваемое алгоритмом в худшем случае.
• Обозначение Big-omega(Ω) : Обозначает наилучшее время выполнения алгоритма.
• Обозначение Big-Theta(Θ): Обозначает среднюю временную сложность случая.

Как измерить сложности?

Ниже приведены некоторые основные сложности:

• Константа: если алгоритм выполняется каждый раз одинаковое количество времени, независимо от размера ввода. Говорят, что он демонстрирует постоянную временную сложность.
• Линейный: если время выполнения алгоритма линейно пропорционально размеру входных данных, то говорят, что алгоритм демонстрирует линейную временную сложность.
• Экспоненциальный: если время выполнения алгоритма зависит от входного значения, возведенного в степень, то говорят, что он демонстрирует экспоненциальную временную сложность.
• Логарифмический: когда время выполнения алгоритма увеличивается очень медленно по сравнению с увеличением размера входных данных, т. е. логарифмически по размеру входных данных, говорят, что алгоритм демонстрирует логарифмическую временную сложность.

Что такое логарифм ?

The power to which a base needs to be raised to reach a given number is called the logarithm of that number for the respective base.
For finding logarithmic two necessary factors that need to be known are base and number. 

Примеры:

logarithm of 8 for base 2 = log₂(8) = 3, 
Explanation: 2³ = 8 Since 2 needs to be raised to a power of 3 to give 8, Thus logarithm of 8 base 2 is 3.

logarithm of 81 for base 9 = log₉(81) = 2,
Explanation: 9² = 81 Since 9 needs to be raised to a power of 2 to give 81, Thus logarithm of 81 base 9 is 2.

Примечание. Экспоненциальная функция является полной противоположностью логарифмической функции . Когда значение многократно умножается, говорят, что оно растет экспоненциально, тогда как когда значение многократно делится, говорят, что оно растет логарифмически.

Различные типы логарифмических сложностей

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

1. Простая логарифмическая сложность (Log _a b)

Простая логарифмическая сложность относится к логарифму b по основанию a . Как уже упоминалось, это относится к временной сложности с точки зрения базы а. При разработке и анализе алгоритмов мы обычно используем 2 в качестве основы для логарифмической сложности времени. На приведенном ниже графике показано, как ведет себя сложность простого журнала.

Существует несколько стандартных алгоритмов с логарифмической временной сложностью:

• Сортировка слиянием
• Бинарный поиск
• Куча сортировки

2. Двойной логарифм (log log N)

Двойной логарифм — это степень, в которую нужно возвести основание , чтобы получить значение x, такое, что при возведении основания в степень x оно достигает значения, равного заданному числу.

Пример:

logarithm (logarithm (256)) for base 2 = log₂(log₂(256)) = log₂(8) = 3. 

Explanation: 2⁸ = 256, Since 2 needs to be raised to a power of 8 to give 256, Thus logarithm of 256 base 2 is 8. Now 2 needs to be raised to a power of 3 to give 8 so log₂(8) = 3.

3. N логарифм N (N * log N)

N*logN сложность относится к произведению N и log N по основанию 2 . N * log N временная сложность обычно наблюдается в алгоритмах сортировки, таких как быстрая сортировка, сортировка слиянием, сортировка кучей. Здесь N — размер структуры данных (массива) для сортировки, а log N — среднее количество сравнений, необходимых для размещения значения в нужном месте в отсортированном массиве.

4. логарифм ² N (log ² N)

log ² N сложность относится к квадрату log N по основанию 2 .

5. N ² логарифм N (N ² * log N)

N ² *log N сложность относится к произведению квадрата N и логарифма N по основанию 2 . Этот порядок временной сложности можно увидеть в случае, когда трехмерную матрицу N * N * N необходимо отсортировать по строкам. Сложность сортировки каждой строки будет N log N, а для N строк будет N * (N * log N). Таким образом, сложность будет N ² log N,

6. N ³ логарифм N (N ³ log N)

N ³ *log N сложность относится к произведению куба N и логарифма N по основанию 2 . Этот порядок временной сложности можно увидеть в случаях, когда матрицу N * N нужно отсортировать по строкам. Сложность сортировки каждой строки будет равна N log N, а для N строк будет N * (N * log N), а для N ширины будет N * N * (N log N). Таким образом, сложность будет N ³ log N,

7. логарифм √N (log √N)

сложность log √N относится к логарифму квадратного корня из N по основанию 2 .

Примеры для демонстрации логарифмической временной сложности

Пример 1: войти _a b

Задача: у нас есть число N , начальное значение которого равно 16 , и задача состоит в том, чтобы уменьшить данное число до 1 путем многократного деления на 2.
Подход:

• Инициализируйте переменную number_of_operation со значением 0 .
• Запустите цикл for от N до 1.
  • В каждой итерации уменьшайте значение N вдвое.
  • Увеличьте переменную number_of_operation на единицу.
• Возвратите переменную number_of_operation.

Реализация:

Объяснение:

Из приведенного выше алгоритма видно, что на каждой итерации значение делится на 2, начиная с 16 и до достижения 1, требуется 4 операции.

Поскольку входное значение уменьшается в 2 раза, с точки зрения математики количество операций, необходимых в этом случае, составляет log ₂ (N), т. е. log ₂ (16) = 4. Таким образом, с точки зрения временной сложности, приведенный выше алгоритм для завершения требуется логарифмическое время выполнения, т.е. log ₂ (N) .

Пример 2: Алгоритм бинарного поиска (log N)

Линейный поиск значения в массиве размера N может быть очень беспокойным, даже если массив отсортирован, но с помощью бинарного поиска это можно сделать намного проще и за меньшее время, поскольку алгоритм уменьшает пространство поиска наполовину в каждой операции. таким образом, сложность составляет логарифм ₂ (N). Здесь основание равно 2, потому что процесс многократно сокращается до половины.

Рассмотрим массив Arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18}. Если требуется найти индекс 8, то алгоритм будет работать следующим образом:

Объяснение:

Двоичный поиск работает по принципу «разделяй и властвуй» . В приведенном выше примере в худшем случае потребуется 3 сравнения, чтобы найти любое значение в массиве. Также значение log (N), где N — размер входных данных, т. е. 8, для приведенного выше примера будет равно 3. Следовательно, можно сказать, что алгоритм демонстрирует логарифмическую временную сложность.

Пример 3: Алгоритм бинарного поиска (log log N)

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

В приведенном выше примере сложность поиска простых чисел в диапазоне от 0 до N составляет O(N * log (log (N))).

Практические задачи на логарифмическую временную сложность

Сравнение различных логарифмических временных сложностей

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

Часто задаваемые вопросы (FAQ) о логарифмической сложности времени:

1) Почему логарифмическая сложность не нуждается в основании?

Логарифмы по любому основанию, т.е. 2, 10, е, можно преобразовать в любое другое основание с добавлением константы, поэтому основание логарифма не имеет значения.

2) Как логарифмы используются в реальной жизни?

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

3) Является ли логарифм повторным делением?

Логарифм — это повторяющееся деление по основанию b до тех пор, пока не будет достигнуто 1. Логарифм - это количество делений на b. Повторное деление не всегда дает ровно 1.

4) В чем разница между логарифмом и алгоритмом?

Алгоритм — это пошаговый процесс решения определенной проблемы, тогда как логарифм — это показатель степени.

5) Почему бинарный поиск логарифмический?

Двоичный поиск — это метод поиска по принципу «разделяй и властвуй», его ключевая идея — сократить пространство поиска до половины после каждого сравнения для нахождения ключа. Таким образом, пространство поиска многократно сокращается вдвое, а сложность становится логарифмической.

6) Что быстрее N или log N?

log N быстрее, чем N, поскольку значение log N меньше, чем N.

7) Что быстрее O(1) или O(log N)?

O (1) быстрее, чем O (log N), поскольку O (1) постоянная временная сложность и самая быстрая из возможных.

8) Какова временная сложность в лучшем случае?

В лучшем случае необходимо выполнять постоянное количество операций независимо от значения N. Таким образом, временная сложность в лучшем случае будет O (1), т.е. наиболее оптимальная временная сложность.

Вывод

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