O(N*log(log(N)算法？

Question

任务描述在这里：https://codility.com/demo/take-sample-test/peaks也在这里：谦卑高峰复杂性

首先，我试着自己解决这个问题，但是我只想出了一个我认为是蛮力的解决方案。然而，它的得分是100分：https://codility.com/demo/results/demoRNWC3P-X4U

显然我完全不满意。)对N的每个因子(或每个峰值，以较小的值为准)调用外部循环，对每个峰值调用内部循环(只需检查每个块中是否有一个峰值)。也许这是O(N^2)，也许更好一些(因为它在时间限制内通过了测试)，但我几乎可以肯定它不是O(N*log(log(N)))。

然后，我尝试寻找一个O(N*log(log(N)))解决方案，但其他人似乎都有一个与我的解决方案非常相似的解决方案。

那么，是否有人对O(N*log(log(N))) (或更好的)解决方案有一个想法？

而且，如果有人能告诉我我的解决方案有多复杂，我会很感激的。

Answer 1

您的代码是O(n ( n ))，其中d(n)是n的除数，在1,100000上，d(n)在83160 = 2^ 3 ^3 ^3 5 7 11时最大，其中有126个除数。根据维基百科，d(n)对于每一个epsilon>0都是o(n^epsilon)，所以生长得相当慢。

要获得O(n日志日志n)解决方案，请构建一个部分和数组，告诉您每个点还剩下多少峰值。然后你就可以知道在O(1)时间间隔中是否有一个峰值。然后检查除数d需要O(n/d)时间。所有除数d上的n/d相加等于所有除数d上的d，结果是，根据相同的Wikipedia页面，O(n log n)。

Answer 2

我用tmyklebu推荐的方式实现了一个解决方案(谢谢！)应该是n.log(log(n))。谦逊不再测试这个问题的“性能”(!)但python解决方案的准确率为100%。

顺便说一句，如果您一直在做Codility课程，那么您将从第8课:素数和复合数中记住，调和数运算的和将给O(log(n))复杂性。我们有一个简化的集合，因为我们只看因子分母。第9课:埃拉托斯提尼筛显示素数倒数之和是O(log(log(N)，并声称“证明不是平凡的”。除数倒数和不同于素数倒数和，但我建议它也属于“非平凡”证明范畴！

def solution(data):

    length = len(data)

    # array ends can't be peaks, len < 3 must return 0    
    if len < 3:
        return 0

    peaks = [0] * length

    # compute a list of 'peaks to the left' in O(n) time
    for index in range(2, length):
        peaks[index] = peaks[index - 1]

        # check if there was a peak to the left, add it to the count
        if data[index - 1] > data[index - 2] and data[index - 1] > data[index]:
            peaks[index] += 1

    # candidate is the block size we're going to test
    for candidate in range(3, length + 1):

        # skip if not a factor
        if length % candidate != 0:
            continue

        # test at each point n / block
        valid = True
        index = candidate
        while index != length:

            # if no peak in this block, break
            if peaks[index] == peaks[index - candidate]:
                valid = False
                break

            index += candidate

        # one additional check since peaks[length] is outside of array    
        if index == length and peaks[index - 1] == peaks[index - candidate]:
            valid = False

        if valid:
            return length / candidate

    return 0