java - Boyer-Moore 多数表决算法的内存复杂度？

Question

根据我的理解，找到多数元素的 Boyer-Moore 多数表决算法是 O(1)，即它是常数，与输入的大小不成比例。那为什么要wiki link提到对数空间 {\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;
    }

Answer 1

这就是为什么维基百科不能总是可靠的原因，至少在读者没有一些批判性思考的情况下不能。 (这不应被视为不使用维基百科的理由；它是一个非常宝贵的资源，这要归功于庞大而忠诚的志愿者贡献者团队。)

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

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

虽然有些算法涉及对足够大的数字进行算术运算以进行准确分析，但实际上没有实际算法涉及如此多的输入以至于值地址的大小(在random access machine ) 需要考虑在内。整个宇宙中没有 2²⁵⁶ 个亚原子粒子，因此可以完全合理地假设一个有限位宽的寄存器足以满足任何寻址目的，包括计算参与对象的数量。

因此，将需要维护输入计数的算法分类为 Θ(log N)(或 O(log N))，只是因为计数器可能有在某些替代宇宙中任意数量的位充其量只是迂腐，并且(在我看来)对理解给定算法的复杂性没有任何贡献。

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