Почему журнал появляется так часто в алгоритмической сложности?

Question

Этот вопрос касается того, существует ли какое-то абстрактное сходство между решениями, которое приводит к появлению в журнале таких проблем, как сортировка и поиск. Или, проще говоря, почему журнал появляется так часто в алгоритмической сложности?

Answer 1

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

Типичным примером было бы многократное удаление половины набора данных, как это делается в бинарном поиске. Это дает O(log2(n)) сложность. Некоторые алгоритмы сортировки работают путем многократного разбиения набора данных пополам, и поэтому также имеют логарифмический термин в своей временной сложности.

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

Answer 2

log появляется очень часто в информатике из-за логической логики. Все может быть уменьшено до истинного против ложного или 1 против 0, или быть или не быть. Если у вас есть if Заявление у вас есть один вариант, в противном случае у вас есть другой вариант. Это может быть применено к битам (у вас 0 или 1) или к серьезным проблемам, но решение есть. И как в реальной жизни, когда вы принимаете решение, вас не волнуют проблемы, которые могли бы возникнуть, если бы вы решили иначе. Вот почему журнал₂(n) появляется очень часто.

Затем каждая более сложная ситуация (например, выберите одно возможное состояние из 3 состояний) может быть уменьшена до log₂(n) => база логарифма не имеет значения (константа не влияет на тренд для функции - она имеет такую ​​же степень):

• Математическое доказательство:

            loga(y)      1
  logx(y) = ------- = -------- * loga(y) = constant * loga(y)
            loga(x)    loga(x)
  

• Доказательство для программистов:

  switch(a) { 
      case 1: ... ;
      case 2: ... ;
      ...
      default: ... ;
  }
  

  похож на:

  if (a == 1) {  
      ...
  } else {
      if ( a == 2 ) {
          ...
      }
      ...
  }
  

  (а switch за k варианты эквивалентны k-1if-else заявления, где k = постоянный)

Но зачем регистрироваться? Потому что это обратное для экспоненты. При первом решении вы разбиваете большую проблему на 2 части. Тогда вы разбиваете только "хорошую" половину на 2 части и т. Д.

n      = n/2^0         // step 1
n/2    = n/2^1         // step 2
n/4    = n/2^2         // step 3
n/8    = n/2^3         // step 4
...
n/2^i  = n/2^i         // step i+1

Q: сколько шагов?

A: я +1 (от 0 до я)

Потому что он останавливается, когда вы находите нужный элемент (других решений вы не можете принять) => n = 2^i, Если мы применим логарифм, основание 2:

log2(n) = log2(2^i)
log2(n) = i
=> i + 1 = log2(n) + 1

Но константа не влияет на сложность => у вас есть ~log₂(n) шагов.

Answer 3

log очень часто встречается в сложности алгоритмов, особенно в рекурсивных алгоритмах.

давайте возьмем для бинарного поиска, например.

у вас есть отсортированный массив A из 100 элементов, и вы ищете число 15..

в бинарном поиске вы посмотрите на средний элемент (50) и сравните его с 15.. если элемент больше 15, то вы найдете средний элемент между 50 и 100, что составляет 75.. и сравните снова... если 15 больше, чем элемент на 75, тогда вы смотрите на элемент между 75 и 100, который является элементом 87... вы продолжаете делать это, пока не найдете элемент или пока не останется больше среднего числа...

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

поэтому первый проход даст вам O(n/2) сложность.. следующий проход будет O(n/4)... O(n/8) и т. д... для представления этого шаблона мы используем журналы..

так как мы сокращаем количество элементов для поиска пополам с каждым проходом алгоритма, который становится основой журнала, поэтому двоичный поиск приведет к сложности O(log2(n))

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