n-е число, не являющееся числом Фибоначчи

Как найти n-е не-число Фибоначчи в o(logn)
не-числа Фибоначчи: 4,6,7,9,10....
Приведенная ниже функция дает не-число Фибоначчи для данного значения n

static int nonFibonacci(int n){
    int a=1,b=2,c=3;
    while(n>0){
        a=b;
        b=c;
        c=a+b;
        n-=(a-1);
    }
    n+=(a-1);
    return (n+b);
}

это дает правильный ответ, но я хочу оптимизировать его. Используя матричное умножение, можно найти число Фибоначчи в o(logn), как применить это свойство для нахождения n-го числа Фибоначчи.

Источник

2 ответа

Алгоритм в вашем фрагменте не O(n) потому что ряд Фибоначчи растет в геометрической прогрессии. Таким образом, это займет у вас O(log n) шаги, чтобы получить больше, чем п. Следующий (и очень простой "тест"), кажется, подтверждает, что ваш код уже имеет правильную сложность:

public class Benchmark {
    public static void main(String[] args) {
        long n = 2;
        for (int i=0 ; i<62 ; i++, n *= 2) {
            long executionTimeNanos = timedExecution(n);
            System.out.println(n + " " + executionTimeNanos + " " + executionTimeNanos/Math.log(n));
        }
    }

    private static long timedExecution(long n) {
        long start = System.nanoTime();
        nonFibonacci(n);
        return System.nanoTime() - start;
    }

    private static long nonFibonacci(long n) {
        long a = 1, b = 2, c = 3;
        while (n > 0) {
            a = b;
            b = c;
            c = a + b;
            n -= (a - 1);
        }
        n += (a - 1);
        return (n + b);
    }
}

Выход:

2 3421 4935.459734881144
4 2566 1850.97773746054
8 855 411.16808665335464
16 2566 925.48886873027
32 1283 370.195547492108
64 855 205.58404332667732
128 1283 264.4253910657915
256 1283 231.3722171825675
512 856 137.21632833343918
1024 1283 185.097773746054
2048 1711 224.40465590554695
4096 1711 205.70426791341805
8192 1283 142.38290288158
16384 1710 176.2148942800091
32768 1283 123.39851583070268
65536 1283 115.68610859128376
131072 1283 108.88104338003177
262144 1710 137.05602888445154
524288 1711 129.91848499794824
1048576 1283 92.548886873027
2097152 1710 117.47659618667274
4194304 1711 112.20232795277347
8388608 1710 107.26123999652728
16777216 1711 102.85213395670903
33554432 1711 98.73804859844066
67108864 1710 94.88494307385106
134217728 1710 91.37068592296768
268435456 2138 110.16007133645014
536870912 2138 106.36144818691737
1073741824 1711 82.28170716536722
2147483648 2138 99.49941927163238
4294967296 2566 115.68610859128376
8589934592 2138 93.46915143698799
17179869184 2993 126.99959580531375
34359738368 2565 105.72893656800545
68719476736 2138 85.68005548390566
137438953472 2566 100.0528506735427
274877906944 2566 97.41988091897579
549755813888 6415 237.30483813596666
1099511627776 2138 77.11204993551509
2199023255552 2566 90.29159694929464
4398046511104 2138 73.44004755763342
8796093022208 2566 86.09198778886233
17592186044416 2566 84.13535170275182
35184372088832 2566 82.26567722046845
70368744177664 2566 80.47729293306696
140737488355328 2566 78.76501010470383
281474976710656 2565 77.09401624750399
562949953421312 2566 75.55011173308327
1125899906842624 2994 86.38857904843113
2251799813685248 2994 84.69468534159914
4503599627370496 2993 83.03819725732053
9007199254740992 2994 81.498659479652
18014398509481984 5132 137.10946203411407
36028797018963968 2994 78.53507186221012
72057594037927936 2993 77.10689745322621
144115188075855872 2993 75.7541448663275
288230376151711744 13257 329.7553130528446
576460752303423488 3421 83.65185991323972
1152921504606846976 2994 71.99048254035928
2305843009213693952 3421 80.9091759816581
4611686018427387904 3421 79.60418927227651

Как видите, даже при n = 2^62 время выполнения составляет всего 3421 наносекунду, это явно не линейно. Соотношение executionTime/log(n) кажется довольно стабильным в конце и составляет около 80, что делает ваше решение O(n),

Я думаю, что изменения, которые мы наблюдаем в начале, связаны со вторым слагаемым ряда Фибоначчи. В самом деле, Fn = (phi^n - psi^n)/sqrt(5) with phi = (1 + sqrt(5))/2 > 1 and psi = (1 - sqrt(5))/2 < 1, Когда п мало, psi^n все еще влияет на результат, но поскольку он меньше 1, он становится очень маленьким, когда n велико, поэтому он становится логарифмическим в конце, а не в самом начале.

Источник

Нетрудно показать, что нашим целевым значением является (n + k), где F k - это наибольшее число Фибоначчи, которое меньше нашей цели. Таким образом, все, что нам нужно сделать, это найти k.

Вы можете сделать это за O (log log n), используя бинарный поиск (с умножением матрицы).

Вы можете сделать это за время O (1), инвертировав выражение для замкнутой формы для F k в терминах k.

Источник
Другие вопросы по тегам