Учет непостоянной временной сложности математических операций (огромное количество) - PullRequest
Новая
       7

Учет непостоянной временной сложности математических операций (огромное количество)

0 голосов
/ 03 марта 2012

С учетом псевдокода: 

e = 1
sum = 1
for i=2 upto n
  e *= 10
  sum += i * e

Выполнение экспоненциального умножения иска, так как оно намного быстрее.Предполагая, что n может быть 10 ^ 1000 или больше, как бы вы получили большие обозначения O для чего-то вроде этого.

Конечно, это будет минимум O (n), но сколькоумножение и сложение увеличивают сложность.Опять же, с большими числами.

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

1 Ответ

2 голосов
/ 05 марта 2012

Чтобы это работало с n, равным 10 ^ 1000, вам определенно необходимо использовать реализацию BigNumber для арифметических операций.

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

В этом случае все, что вам нужно сделать, это включить эту сложность в свой алгоритм выше, чтобысложная сложность.

Например, если у вас есть: 

for i = 2 to n
   <multiplication operation>

Предполагая, что умножение является квадратичным по размеру (# бит) n, то O(mult) = (log n) ^ 2.Тогда сложность большого цикла цикла for будет равна: 

n * O(mult) = O(n * ((log n) ^ 2))

В вашем примере цикл for содержит три потенциально "дорогих" операции: 

for i = 2 to n
   e *= 10          //   e = e * 10
   sum += i * e     //   sum = sum + i * e

.дорогостоящие операции: mult1: e*10, mult2: i * e и add: sum + (result of i*e)

Их совокупная сложность составит O(mult1 + mult2 + sum), что примет значение наибольшего из трех.В этом случае, безусловно, mult2

Так что, если вы можете получить оценку для операции умножения, то общая сложность будет, как указано выше: n * O(mult), что опять-таки, предполагая квадратичную реализациюв размере чисел, собирается перевести что-то вроде: O (n * log (n))

Что касается оценки характеристик времени выполнения арифметических операций, вот хорошая таблица изВикипедия различных алгоритмов для основных арифметических операций .

...