Время работы Math.Pow - const?

130
03 января 2022, 06:10

Есть 2 функции, находящие n-ное число Фибоначчи. Первое находит через фор-лу Бине O(Log N), второе через метод итераций O(n).

static double SQRT5 = Math.Sqrt(5);
static double PHI = (SQRT5 + 1) / 2;
public static int Bine(int n)
{
    return (int)(Math.Pow(PHI, n) / SQRT5 + 0.5);
}

static long[] NumbersFibonacci = new long[35];
public static void Iteracii(int n)
{
NumbersFibonacci[0] = 0;
NumbersFibonacci[1] = 1;
for (int i = 1; i < n - 1; i++)
    {
        NumbersFibonacci[i + 1] = NumbersFibonacci[i] + NumbersFibonacci[i - 1];
    }
}

Но для нахождения 35 члена последовательности фор-ла Бине работает по времени хуже, чем метод итераций. При этом если вместо 35 написать достаточно большое число, например 1000000 (чисто в целях эксперимента), то время работы для фор-лы Бине не изменится, но для метода итераций возрастёт в несколько раз.

В связи с этим вопрос, сложность Math.Pow, который используется в фор-ле Бине (из-за которого такое время работы) на самом деле const, и если да, то как это доказать?

Answer 1

Очень просто доказать, что существует алгоритм работающий за константное время при определенных условиях, а значит в библиотечной функции скорее всего будет использован как минимум не худший алгоритм.

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

Каждая операция умножения даже для не самого оптимального алгоритма требует O(n*m) элементарных операций, где n и m - количество бит в соответствующих числах.

Для каких нибудь бесконечных числовых типов константой тут и не пахнет, но в вашем случае используются типы с фиксированным количеством бит - double и int, а значит все эти n и m превращаются в тыкву – константы, следовательно и сам алгоритм возможно реализовать за O(1).

Важное замечание

Ваш алгоритм способен работать только с очень небольшими аргументами, так вы еще и ограничиваете результат интом. Если программа действительно должна иметь возможность вычислять F1000000 как в примере, имейте в виду, что результат будет занимать сотни тысяч бит и без неограниченных числовых типов вам не обойтись, а значит и константной сложности ждать не стоит.

READ ALSO
Проблемы с бд C#
c#

Проблемы с бд C#

Всем привет, суть проблемы то что я делаю "Регистрацию" для этого я делаю проверки что бы небыло одинаковых логинов делаю проверку:

 101
Как в дочернем потоке приостановить выполнение кода , вы полнить метод в основном потоке , а потом продолжить выполнение дочернего потока?
c#

Как в дочернем потоке приостановить выполнение кода , вы полнить метод в основном потоке , а потом продолжить выполнение дочернего потока?

Постоянно сталкиваюсь с ошибкой :

 208
SESSION не изменяется
PHP

SESSION не изменяется

Через fetch в файл сorephp отправляется action, который равен 'login', а так же email и epass

 245
Проблема включения Apache в утилите MAMP
PHP

Проблема включения Apache в утилите MAMP

Во время нажатия кнопки Start Server загорается зеленый круг на Apache,через 1 секунду уже на MySQL,затем с Apache пропадает зеленый круг и остается только...

 194