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

Question

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

Answer 1

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

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

В целом, логарифмы часто обнаруживаются в решениях для divide-and-conquer рекуррентных отношений. См. Master Theorem в Википедии для дальнейшего обсуждения.

Answer 2

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

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

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

    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) { 
       ... 
      } 
      ... 
  } 
  

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

Но почему журнал? Потому что это инверсная для экспоненты. При первом решении вы разбиваете большую проблему на две части. Тогда вы нарушаете только «хорошую» половину в 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: Сколько шагов есть?

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

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

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

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

Answer 3

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

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

у вас есть отсортированный массив А 100 элементов и ваш ищут номер 15 ..

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

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

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

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

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