时间戳

首页 > 解决方案 > 这可以在 O(logN) 复杂度中完成吗？

algorithm - 这可以在 O(logN) 复杂度中完成吗？

问题描述

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

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

标签： algorithmbinary-search

解决方案

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

与 nm 所指出的类似，如果 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) - 如果每个版本都变得更糟。请注意，递归不会继续进入没有减速的段。

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

编辑：使用提供的更坏提交函数（而不是performance列表），使 O 表达式更紧凑，固定缩进，添加关于 k=0 的 O() 的说明，并修复错字（缺少参数）。

推荐阅读