优化 Codility 标志的性能 Python

Question

我写了下面的算法作为 Codility Flags 的解决方案。这通过了正确性检查，但是它在大多数性能检查中超时。

这个的复杂度应该是 O(m**2)，其中 m 是 A 中的峰数，n 是 A 的长度。但是，while potentialK > maxFlags 循环应该只执行到找到满足条件的合适数量的标志为止。我不确定如何针对时间复杂度进一步优化它。

def solution(A):
    peaks = []
    distances = []
    if len(A) == 1: return 0
    for i in range(1, len(A) -1): 
        if A[i] > A[i-1] and A[i] > A[i+1]:
            if len(distances) == 0: 
                distances.append(i)
            else: 
                distances.append(i - peaks[-1]) 
            peaks.append(i)
    if len(peaks) == 0: return 0
    if len(peaks) == 1: return 1
    if len(peaks) == 2: return 2 if peaks[1] - peaks[0] >= 2 else 1
    potentialK = len(peaks)    
    maxFlags = 0 
    while potentialK > maxFlags: 
        cumDistance = 0 
        flags = 0
        firstFlag = True
        for i in range(1, len(distances)):
            cumDistance += distances[i]
            if cumDistance >= potentialK: 
                if firstFlag: 
                    flags += 2 
                    firstFlag = False
                else: 
                    flags += 1
                cumDistance = 0
        if flags > maxFlags and flags == potentialK: 
            return flags 
        elif flags > maxFlags and potentialK > flags: 
            maxFlags = flags
        potentialK -= 1
    return maxFlags

Answer 1

我设法优化如下：

由于各个标志之间的距离必须 >= 标志的数量，我们知道标志的最大数量将是 peaks 的最后一个元素的根 - peaks 的第一个元素：sqrt(peaks[-1] - peaks[0])

然后我能够将 potentialK 的初始值更新为

potentialK = math.ceil(math.sqrt(peaks[-1] - peaks[0]))

这应该会大大减少外部 while 循环的迭代次数。

import math 

def solution(A):
    peaks = []
    distances = []
    if len(A) == 1: return 0
    for i in range(1, len(A) -1): 
        if A[i] > A[i-1] and A[i] > A[i+1]:
            if len(distances) == 0: 
                distances.append(i)
            else: 
                distances.append(i - peaks[-1]) 
            peaks.append(i)
    if len(peaks) == 0: return 0
    if len(peaks) == 1: return 1
    if len(peaks) == 2: return 2 if peaks[1] - peaks[0] >= 2 else 1
    potentialK = math.ceil(math.sqrt(peaks[-1] - peaks[0]))  
    maxFlags = 0 
    while potentialK > maxFlags: 
        cumDistance = 0 
        flags = 0
        firstFlag = True
        for i in range(1, len(distances)):
            cumDistance += distances[i]
            if cumDistance >= potentialK: 
                if firstFlag: 
                    flags += 2 
                    firstFlag = False
                else: 
                    flags += 1
                cumDistance = 0
        if flags > maxFlags and flags == potentialK: 
            return flags 
        elif flags > maxFlags and potentialK > flags: 
            maxFlags = flags
        potentialK -= 1
    return maxFlags

Answer 2

您的算法是 O(n^2)，因为输入中可能有 O(n) 个峰值。加快算法速度取决于您提前知道输入大小这一事实。

观察答案是[1, ceil(sqrt(n))]区间内的整数。任何小于 1 的距离要求都意味着您不能放置任何标志。由于距离要求，您不能放置超过 ceil(sqrt(n)) 的标志，即使每个元素都以某种方式成为峰值（这是不可能的）。

因此，您可以进行的一项优化是您只需要检查 O(sqrt(n)) potentialK 值。（你发布这个作为你自己问题的答案。）这将使运行时间下降到 O(n^(3/2))，因为 m 是 O(n)，这显然足够快以通过 Codility 的测试，但是我认为运行时仍然可以改进（正确性也可以）。

我们可以再做一个观察：

存在一个正整数 i 使得：

对于每个 j，j 是小于 i 的正整数，我们可以放置至少相隔 j 距离的 j 个标志，并且
对于每个 j，j 是大于 i 的正整数，我们不能放置至少相隔 j 距离的 j 个标志。

这使我们能够使用二进制搜索：

import math

def does_distance_work(peaks, distance):
    peak_count = 1
    last_peak = peaks[0]
    for i in range(len(peaks)):
        if peaks[i] >= last_peak + distance:
            peak_count += 1
            last_peak = peaks[i]
        
    return peak_count >= distance


def solution(A):
    # Get the indices of the peaks.
    peaks = []
    for i in range(1, len(A) - 1):
        if A[i] > A[i - 1] and A[i] > A[i + 1]:
            peaks.append(i)
    
    # Return 0 if no peaks.
    if not peaks:
        return 0
    
    # Check maximum value.
    if does_distance_work(peaks, math.ceil(math.sqrt(len(A)))):
        return math.ceil(math.sqrt(len(A)))

    # If neither of the above two checks apply, find the largest i (as specified above) using binary search.
    low, high = 1, math.ceil(math.sqrt(len(A))) - 1
    while low <= high:
        mid = low + (high - low) // 2
        mid_valid_distance = does_distance_work(peaks, mid)
        mid_plus_one_valid_distance = does_distance_work(peaks, mid + 1)
        if not mid_valid_distance:
            high = mid
        elif mid_plus_one_valid_distance:
            low = mid + 1
        else:
            return mid
    
    # If we've reached this line, something has gone wrong.
    return -1

递归到 O(log(sqrt(n)) 的深度，二分搜索的每次迭代都需要 O(n)。最后的运行时间是 O(n * log(sqrt(n) ))，它应该（并且确实）通过了性能测试。

优化 Codility 标志的性能 Python

Optimising Performance of Codility Flags Python

python

algorithm

time-complexity