Получение временной сложности из анализа времени выполнения

Question

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

Я спрашиваю об этом, потому что я написал алгоритм на C ++, который в основном выполняет затенение пикселей на 2D-изображениях, используя одно ядро ​​процессора и один поток (процессор 3GHZ). Я измерил время выполнения при размерах ввода от 2^4 до 2^30, что представляет собой матрицу размером 32,768 ** 2. Теперь у меня есть этот график того, как моя среда выполнения ведет себя в зависимости от моего входного размера n:

Итак, для входного размера n = 2^4 to 2^30 точное время выполнения было (по строкам):

 [1]  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 [8]  0.000  0.000  0.000  0.000  0.001  0.000  0.000
[15]  0.002  0.004  0.013  0.018  0.053  0.079  0.231
[22]  0.358  0.963  1.772  4.626  9.713 25.582

Теперь это немного странно, потому что, когда степень двойки меняется с нечетной на четную, время выполнения увеличивается всего на 1,5, но когда оно меняется с четного на нечетное, время выполнения увеличивается втрое. Итак, когда я удваиваю свой ввод, время выполнения увеличивается в среднем кратно (3 + 1.5) / 2 = 2.25. Фактически, кажется, что, когда n становится произвольно большим, оба изменения аргумента мощности от Odd to even и even to Odd вызывают умножение времени выполнения на константу 2,25, другими словами: когда n становится больше, множитель времени выполнения сходится к 2,25.

Если мой алгоритм довольно сложен, есть ли способ сказать что-нибудь о его временной сложности из этого анализа?

Answer 1

Наличие C(4 * n) = (1.5 * 3) * C(n) предполагает, что у вас есть сложность в O(n^1.08) - где 1.08 ~ log(4.5)/log(4).

Конечно, это всего лишь подсказка, и мы ничего не можем доказать асимптотически.

Answer 2

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

Например, мы можем сказать это скорее всего, растет быстрее, чем quadrati c, поскольку решение констант для f (30) и последующее вычисление того, что мы ожидали для f (20), дает слишком большое число, подразумевая, что наша функция асимптотически растет намного быстрее, чем квадратично . Если мы предположим экспоненциальную функцию и решим константы в f (30), мы получим ожидаемое значение для f (20), которое намного ближе к фактическому числу (хотя и немного ниже, поэтому наша функция может расти немного медленнее. чем A * 2 ^ n ... но мы могли бы, вероятно, ввести новый коэффициент B, чтобы найти A * 2 ^ (Bn) и приблизиться).

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

На самом деле это похоже, что ваша функция поочередно удваивает значения и утроивает их. Если это действительно так, то можно ожидать, что каждые два приращения n будут давать шестикратное увеличение; квадрат root из 6 составляет около 2,45, поэтому ваша функция действительно может быть экспоненциальной, например A * 2,45 ^ n, или, по крайней мере, это может дать лучшее соответствие, чем использование базы 2.