这可以在O(logN)复杂度内完成吗？

Question

您正在处理一个项目，并且您注意到在两个版本之间存在性能下降。你有一个函数：

boolean worseCommit(int commit1, int commit2) 

它运行性能测试，如果commit2比commit1差，则返回true，否则返回false。

找出所有降低了两个版本之间性能的错误提交。假设性能没有提高。

提交Id：1, 2, 3, 4, 5, 6, 7, 8, 9

性能：10, 10, 10, 8, 8, 8, 5, 5, 5

输出4, 7

Answer 1

对于k=0，这可以在O(k=0(n/k))和O(1)中完成，其中k是较慢发布的数量。对于只有一个错误版本的特殊情况，它将需要O(log )操作。

类似于n.m.已经注意到，如果k=n或k未指定，则运行时变为O(n)。

def bad_releases():
    slow = []
    add_slow(slow, 0, num_commits - 1)
    return slow

def add_slow(slow,  min, max)
    if not worseCommit(min, max):
        return
    if min + 1 = max:
        slow.append(max)
        return
    mid = (min + max) / 2
    add_slow(perf, slow, min, mid)
    add_slow(perf, slow, mid, max)

请注意，如果每个版本都变得更糟，那么对slow的插入最多只能运行O(n)。请注意，递归不会继续到没有减速的段中。

我们可以知道在给定的时间间隔内没有减速，这要归功于发布永远不会变快的事实。因此，如果区间的两端具有相同的性能，则意味着整个区间具有相同的性能。

编辑:使用提供的worseCommit函数(而不是performance列表)，使O表达式更紧凑，修复了缩进，添加了有关k=0的O()的说明，并修复了一个拼写错误(缺少参数)。