Codility 的复杂性达到顶峰

我刚刚完成了以下 CodilityPeaks http://codility.com/demo/take-sample-test/peaks问题。问题如下：

给出一个由 N 个整数组成的非空零索引数组 A。 峰值是大于其邻居的数组元素。更准确地说，它是一个索引 P，满足 0 A[P + 1]。 例如下面的数组A：

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

正好有三个峰值：3、5、10。 我们想要将该数组分成包含相同数量元素的块。更准确地说，我们想要选择一个数字 K，它将产生以下块： A[0], A[1], ..., A[K − 1], A[K], A[K + 1], ..., A[2K − 1], ... A[N − K], A[N − K + 1], ..., A[N − 1]。 更重要的是，每个块应该至少包含一个峰值。请注意，块的极端元素（例如 A[K − 1] 或 A[K]）也可以是峰值，但前提是它们具有两个邻居（包括相邻块中的一个）。 目标是找到数组 A 可以分为的最大块数。 数组A可以分为如下的块：

一块 (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2)。该块包含三个峰。

两个块 (1, 2, 3, 4, 3, 4) 和 (1, 2, 3, 4, 6, 2)。每个区块都有一个峰值。

三个块 (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2)。每个区块都有一个峰值。

请特别注意，第一个块 (1, 2, 3, 4) 在 A[3] 处有一个峰值，因为 A[2] A[4]，即使 A[4] 在相邻块。 但是，数组 A 不能分为四个块：(1, 2, 3)、(4, 3, 4)、(1, 2, 3) 和 (4, 6, 2)，因为 (1, 2, 3) 块不包含峰。特别注意 (4, 3, 4) 块包含两个峰值：A[3] 和 A[5]。 数组A最多可以分为3个块。

写一个函数： 类解决方案 { 公共 int 解决方案(int[] A); } 给定一个由 N 个整数组成的非空零索引数组 A，返回 A 可以分为的最大块数。 如果 A 无法分为一定数量的块，则该函数应返回 0。 例如，给定：

A[0] = 1
A[1] = 2 
A[2] = 3 
A[3] = 4 
A[4] = 3 
A[5] = 4 
A[6] = 1 
A[7] = 2 
A[8] = 3 
A[9] = 4 
A[10] = 6 
A[11] = 2

该函数应返回 3，如上所述。 假使，假设：

N是[1..100,000]范围内的整数； 数组 A 的每个元素都是 [0..1,000,000,000] 范围内的整数。

复杂：

预期最坏情况时间复杂度为 O(N*log(log(N)))

预期最坏情况的空间复杂度为 O(N)，超出输入存储（不计算输入参数所需的存储）。

可以修改输入数组的元素。

我的问题

因此，我用对我来说似乎是蛮力解决方案来解决这个问题 - 遍历每个组的大小1..N，并检查每组是否至少有一个峰值。在我试图解决这个问题的前 15 分钟，我试图找出一些更优化的方法，因为所需的复杂性是 O(N*log(log(N)))。

这是我的“暴力”代码，它通过了所有测试，包括大型测试，得分为 100/100：

public int solution(int[] A) {
    int N = A.length;

    ArrayList<Integer> peaks = new ArrayList<Integer>();
    for(int i = 1; i < N-1; i++){
        if(A[i] > A[i-1] && A[i] > A[i+1]) peaks.add(i);
    }

    for(int size = 1; size <= N; size++){
        if(N % size != 0) continue;
        int find = 0;
        int groups = N/size;
        boolean ok = true;
        for(int peakIdx : peaks){
            if(peakIdx/size > find){
                ok = false;
                break;
            }
            if(peakIdx/size == find) find++;
        }
        if(find != groups) ok = false;
        if(ok) return groups;
    }

    return 0;
}

我的问题是如何推断出这实际上是 O(N*log(log(N)))，因为它对我来说一点也不明显，而且我很惊讶我通过了测试用例。我正在寻找即使是最简单的复杂性证明草图，也能让我相信这个运行时。我假设 log(log(N)) 因子意味着在每次迭代中通过平方根减少问题，但我不知道这如何应用于我的问题。非常感谢您的帮助

您是完全正确的：要获得日志日志性能，需要减少问题。

python 中的 n.log(log(n)) 解决方案[如下]。 Codility 不再测试此问题的“性能”（！），但 Python 解决方案的准确性得分为 100%。

正如您已经猜测的那样：外循环将是 O(n)因为它正在测试每个大小的块是否是干净的除数内循环必须是 O(log(log(n)))总体上给出 O(n log(log(n))) 。

我们可以获得良好的内循环性能，因为我们只需要执行 d(n)，即 n 的除数数。我们可以存储前缀和迄今为止的峰值，它使用问题规范允许的 O(n) 空间。检查每个“组”中是否出现峰值是使用组开始和结束索引的 O(1) 查找操作。

按照这个逻辑，当候选块大小为 3 时，循环需要执行 n/3 峰值检查。复杂度变为总和：n/a + n/b + ... + n/n，其中分母 (a, b, ...) 是 n 的因子。

短篇故事：n.d(n) 操作的复杂度为 O(n.log(log(n)))。

更长的版本：如果您参加过 Codility 课程，您会记得第 8 课：素数和合数 https://codility.com/media/train/8-PrimeNumbers.pdf谐波数运算之和将给出 O(log(n)) 复杂度。我们有一个缩减集，因为我们只考虑因子分母。第 9 课：埃拉托斯特尼筛法 https://codility.com/media/train/9-Sieve.pdf展示了素数倒数之和如何为 O(log(log(n))) 并声称“证明是不平凡的”。在这种情况下维基百科 http://en.wikipedia.org/wiki/Divisor_function告诉我们除数之和 sigma(n) 有一个上限（参见罗宾不等式，大约在页面的中间）。

这完全回答了你的问题吗？也非常欢迎有关如何改进我的 python 代码的建议！

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

Credits:感谢 @tmyklebu 的贡献所以答案 https://stackoverflow.com/questions/26150180/onloglogn-algorithm-for-codilitys-peaks这对我有很大帮助。