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

Question

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

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

Answer 2

这就是为什么不能总是依赖维基百科的原因，至少在 reader 方面没有一些批判性思考是这样。（这不应被视为不使用维基百科的理由；由于庞大而忠诚的志愿贡献者团队，它是一个非常宝贵的资源。）

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

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

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

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

尽管如此，学究们和任何人一样有权利为维基百科做贡献；事实上，维基百科文化招致迂腐的理论可能是理论上的。这仍然需要与维基百科坚持认为作者不包括 "original research" 相平衡，这将包括（再次，在我看来）以一种与通常公布的结果相矛盾的方式重新解释算法的存储复杂性。（这或许可以解释相关维基百科文章中的 "citation-needed" 标记。）

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

Memory complexity of Boyer–Moore majority vote algorithm?

java

algorithm

boyer-moore