algorithm - Codility Peaks 复杂性

Question

我刚刚完成了以下 Codility Peaks问题。问题如下:

---

给定一个由 N 个整数组成的非空零索引数组 A。 峰是比其邻居大的数组元素。更准确地说，它是一个索引 P，使得 0 < P < N − 1，A[P − 1] < A[P] 和 A[P] > 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。 我们想把这个数组分成包含相同数量元素的 block 。更准确地说，我们要选择一个数字 K 来产生以下 block : 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]。 更重要的是，每个 block 应该至少包含一个峰。请注意， block 的极端元素(例如 A[K − 1] 或 A[K])也可以是峰值，但前提是它们具有两个邻居(包括相邻 block 中的一个)。 目标是找到数组 A 可以划分成的最大块数。 数组A可以分块如下:

一个 block (1、2、3、4、3、4、1、2、3、4、6、2)。该 block 包含三个峰。

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

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

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

写一个函数: 类解决方案 { public int 解决方案(int[] A)； } 即，给定一个由 N 个整数组成的非空零索引数组 A，返回 A 可以分成的最大块数。 如果 A 不能被分成一定数量的 block ，函数应该返回 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)) 因子意味着在每次迭代中将问题减少平方根，但我不知道这如何适用于我的问题。非常感谢任何帮助

Answer 1

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

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

正如您已经推测的那样: 外循环将是 O(n) 因为它正在测试 block 的每个大小是否是干净的除数 内部循环必须是 O(log(log(n))) 才能得到 O(n log(log(n))) 整体。

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

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

短篇小说: n.d(n) 操作的复杂度为 O(n.log(log(n)))。

更长的版本: 如果您一直在学习 Codility Lessons，您会记得 Lesson 8: Prime and composite numbers调和数运算的总和将给出 O(log(n)) 复杂度。我们有一个缩减集，因为我们只看因子分母。 Lesson 9: Sieve of Eratosthenes显示素数的倒数之和是 O(log(log(n))) 并声称“证明是非平凡的”。在这种情况下 Wikipedia告诉我们除数之和 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

学分: @tmyklebu 的主要荣誉是他的 SO answer这对我帮助很大。