0

根据我的理解，要找到多数元素 Boyer-Moore 多数投票算法是 O(1)，即它是恒定的，并且与输入的大小不成比例。那么为什么 thi wiki 链接提到对数空间 {\displaystyle O(\log n)} O(\log n)

这是供参考的程序

public class MajorityElement {
    /* Function to print Majority Element */
    void printMajority(int a[], int size) {
        /* Find the candidate for Majority */
        int cand = findCandidate(a, size);

        /* Print the candidate if it is Majority */
        if (isMajority(a, size, cand))
            System.out.println(" " + cand + " ");
        else
            System.out.println("No Majority Element");
    }

    /* Function to find the candidate for Majority */
    int findCandidate(int a[], int size) {
        int maj_index = 0, count = 1;
        int i;
        for (i = 1; i < size; i++) {
            if (a[maj_index] == a[i])
                count++;
            else
                count--;
            if (count == 0) {
                maj_index = i;
                count = 1;
            }
        }
        return a[maj_index];
    }

    /*
     * Function to check if the candidate occurs more than n/2 times
     */
    boolean isMajority(int a[], int size, int cand) {
        int i, count = 0;
        for (i = 0; i < size; i++) {
            if (a[i] == cand)
                count++;
        }
        if (count > size / 2)
            return true;
        else
            return false;
    }
4

2 回答 2

1

这就是为什么不能总是依赖维基百科的原因，至少在没有读者进行批判性思考的情况下是这样。（这不应被视为不使用 Wikipedia 的理由；它是一个非常有价值的资源，这要归功于一个庞大而忠诚的志愿者贡献者团队。）

有两种常用的模型来衡量空间和时间复杂度：统一成本模型和对数成本模型。统一成本模型假设单个值的存储成本为Θ(1)（无论该值的大小），并且单个简单算术计算的时间复杂度也是Θ(1). 如果值非常大，则这些简化是不正确的，因此可能需要使用对数模型。在对数模型中，我们不是通过值的计数来衡量问题的大小，而是通过值的总大小（以位为单位）来衡量。（另一篇 Wikipedia 文章提供了对这些模型的讨论。另请参阅参考资料。）

这对简单的算术影响不大。添加两位数字的成本N是Θ(N)和添加总大小为N位的数字向量的成本是Θ(N)，就像问题的大小以值衡量的简化假设和添加两个值是Θ(1)。但是如果涉及乘法和除法，复杂度计算会变得更加复杂，除非数字真的非常非常大，否则真的不值得沿着这条路走下去，例如在各种加密算法中，其中包括对以下值的操作大小为数千位。

虽然有些算法涉及对足够大的数字的算术运算，因此需要将其考虑在内以进行准确的分析，但实际上并没有实际的算法涉及如此多的输入，以至于值的地址大小（在随机存取机器中） ) 需要考虑。整个宇宙中没有 2256 个亚原子粒子，因此完全有理由假设一个有限位宽的寄存器足以用于任何寻址目的，包括计算参与对象的数量。

因此，仅仅因为计数器在某个替代宇宙中可能具有任意数量的位，就将需要维持输入计数的算法分类为Θ(log N)（或O(log N)），充其量是学究气，并且（在我看来）对理解没有任何帮助给定算法的复杂性。

尽管如此，书呆子和任何人一样有权为维基百科做出贡献。事实上，理论上说维基百科文化会招致迂腐。这仍然需要与 Wikipedia 坚持认为作者不包括“原始研究”进行平衡，这将包括（再次，在我看来）以与通常发布的结果相矛盾的方式重新解释算法的存储复杂性。（这可能解释了相关维基百科文章中的“需要引用”标记。）

于 2016-08-28T00:33:33.360 回答
1

这是因为变量count需要O(log(n))位来存储候选的出现次数。当然，在您的日常测试中，您不太可能尝试使用超过 2^32（或类似的）单元格的数组。

于 2016-08-27T15:11:45.923 回答