Блог

Для тех экспертов Big O… Я пытаюсь определить временную сложность функции с помощью двух рекурсивных вызовов, при которых ввод каждый раз уменьшается вдвое:

 function myFunc(n) {
  if (n > 1) {
    let something = 0

    for (let i=0; i < n; i  ) {
      // Do some linear stuff in here
    }

    myFunc(n/2)
    myFunc(n/2)
  }

  return something;
}
  

Я не уверен, как именно сокращение вдвое влияет на анализ. Любая помощь очень ценится!

Первым шагом в анализе рекурсивной функции было бы записать рекуррентное соотношение. В этом случае у вас есть:

 T(n) = 2T(n/2)   O(n)
  

Это одна из наиболее распространенных форм рекуррентных соотношений, поэтому мы можем сразу сформулировать решение без каких-либо дальнейших вычислений:

 T(n) = O(n log n)
  

Этот результат легко доказать с помощью индукции. Смотрите, Например, здесь .