Класс сложности функции с известной зависимостью между временем выполнения и размером ввода

Question

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

Если мы знаем (X), как мы можем найти класс сложности / обозначение функции?Например, если X немного больше 2, то обозначение Big-O будет O (N log N).

Answer 1

Пусть T(n) - временная сложность функции, о которой вы говорите, где n - размер входных данных. Мы можем написать рекурсивное уравнение для T(n):

T(n) = X * T(n/2)

, где X - ваша постоянная. Давайте «развернем» эту рекурсию:

T(n) = X * T(n/2) = X^2 * T(n/4) = X^3 * T(n/8) = ... = X^k * T(n/2^k)

Этот процесс развертывания должен завершиться, когда параметр k станет достаточно большим, чтобы удовлетворить:

n/2^k = 1

, что означает n = 2^k или k = log(n) (логарифм по основанию 2). Также мы можем предположить, что:

T(1) = C

, где C - некоторая другая константа. Теперь мы смотрим на развернутое уравнение и заменим k на log(n) и T(1) на C:

T(n) = X^log(n) * C

Мы можем упростить эту формулу, используя свойства логарифма:

T(n) = C * n^log(X)