Codility FibFrog 算法 - 将时间复杂度从 O(N * log(N) ** N) 提高到 O(N*log(N))

Question

我正在尝试解决 Codility FibFrog 问题，我想出了以下解决方案：

def jumps_from(position, fb, A): 
    paths = set([])
    for i in fb: 
        newPos = position + i
        if newPos == len(A):
            return set([-1])
        elif newPos < len(A):
            if A[newPos] == 1: 
                paths.add(newPos)
        else: break
    return paths
            
def solution(A):
    if len(A) < 3: return 1 
    fibonaccis = fibonacci(len(A))
    if len(A) + 1 in fibonaccis: return 1
    paths = set([-1])
    steps = 0
    while True:
        paths = set([idx for pos in paths for idx in jumps_from(pos, fibonaccis, A)])
        if len(paths) == 0: return -1
        if -1 in paths: 
            return steps + 1
        steps += 1
    return steps 

def fibonacci(N): 
    arr = [0] * (N + 2)
    arr[1] = 1
    for i in range(2, N + 2): 
        arr[i] = arr[i-1] + arr[i-2]
    return dict.fromkeys(arr[2:], 1)

Codility 将此运行时检测为 O(N * log(N) ** N)。

Codility 报告：https://app.codility.com/demo/results/trainingJV7YAC-G3B/

我将其与以下进行比较，后者在 Codility 上得分为 100%，并且运行时间为 O(N * log(N)):

def gen_fib(n):
    fn = [0,1]
    i = 2
    s = 2
    while s < n:
        s = fn[i-2] + fn[i-1]
        fn.append(s)
        i+=1
    return fn

def new_paths(A, n, last_pos, fn):
    """
    Given an array A of len n.
    From index last_pos which numbers in fn jump to a leaf?
    returns list: set of indexes with leaves.
    """
    paths = []
    for f in fn:
        new_pos = last_pos + f
        if new_pos == n or (new_pos < n and A[new_pos]):
            paths.append(new_pos)
    return paths


def solution(A):
    n = len(A)
    if n < 3:
        return 1

    # A.append(1) # mark final jump
    fn = sorted(gen_fib(100000)[2:]) # Fib numbers with 0, 1, 1, 2..  clipped to just 1, 2..
    # print(fn)
    paths = set([-1]) # locate all the leaves that are one fib jump from the start position.

    jump = 1
    while True:
        # Considering each of the previous jump positions - How many leaves from there are one fib jump away
        paths =  set([idx for pos in paths for idx in new_paths(A, n, pos, fn)])

        # no new jumps means game over!
        if not paths:
            break

        # If there was a result in the new jumps record that
        if n in paths:
            return jump
            
        jump += 1

    return -1

我不确定为什么我的解决方案在运行时会有所不同，因为方法完全相同 - 计算可以从 -1 跳转到的所有索引，然后计算可以跳转到的所有索引从新位置开始，直到到达河对岸，否则找不到新位置。

Answer 1

请参考我的第一点。

If len(A) = 100000, you are calculating 100003 fibonacci numbers, while we only need fibonacci numbers which are less than 100k, which would be <30 of them.

当前的 fibonacci 函数仍在返回 N 斐波那契数，而不是仅返回小于 N 的斐波那契数。对于 N=100k，它应该只是 25 个数字，而不是超过 100k。

请将您的 fibonacci 函数更新为此 -

def fibonacci(N):
    arr = [1, 1]
    while arr[-1] < N:
        arr.append(arr[-1] + arr[-2])
    return dict.fromkeys(arr[1:], 1)

我只是运行在本地进行测试，看起来你的 fibonacci 函数需要大约 1 秒来生成第一个 100k 斐波那契数，这就是它可能无法通过性能测试的原因，即使您的其余代码是最佳的。我认为您应该能够在更正 fibonacci 函数后以所需的性能限制清除它。

Codility FibFrog 算法 - 将时间复杂度从 O(N * log(N) ** N) 提高到 O(N*log(N))

Codility FibFrog Algorithm - Improving Time Complexity from O(N * log(N) ** N) to O(N*log(N))

python

algorithm

fibonacci

time-complexity