Оценка временной сложности для биномиального коэффициента

Question

Я новичок в теоретической информатике и хотел бы рассчитать временную сложность следующего алгоритма, который оценивает биномиальный коэффициент, определенный как

nf = 1; 
for i = 2 to n do nf = nf * i; 
kf = 1; 
for i = 2 to k do kf = kf * i; 
nkf = 1; 
for i = 2 to n-k do nkf = nkf * i; 
c = nf / (kf * nkf);

My textbook suggests to use Stirling's approximation

$ n! \ приблизительно \ sqrt {2 \ pi n} \ left (\ frac {n} {e} \ right) ^ {n} $.

Однако я могу получить тот же результат, если учесть, что for i = 2 to n do nf = nf * i; имеют сложность O (n-2) = O (n), что является преобладающим.

Приближение Стирлинга кажется немного перебор. Я ошибаюсь?

Answer 1

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

Однако вы ошибаетесь насчет временной сложности вычисления формулы Стирлинга. Для его вычисления вам понадобится только log (n) в операциях с базой 2. Это связано с тем, что при попытке вычислить p-ю степень некоторого действительного числа вместо умножения его p раз вы можете продолжать возводить число в квадрат, чтобы быстро вычислить его. Например:

Если вы хотите вычислить 2 ^ 17, вместо выполнения 17 таких операций:

return 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2

вы можете сделать это:

a = 2*2
b = a*a
c = b*b
d = c*c
return d * 2

который всего 5 операций.

Примечание: однако имейте в виду, что формула Стирлинга не равна факториалу. Это всего лишь приближение, но хорошее.

Изменить: также вы можете рассматривать ^ n как e ^ (log (a) * n), а затем вычислять его с помощью быстро сходящегося расширения ряда

1 + (журнал (а) п) + ((журнал (а) п) ^ 2) / 2! + ((журнал (а) п) ^ 3) / 3! + ...

Поскольку ряды сходятся очень быстро, вы можете быстро получить действительно близкие приближения.