Boyer多数投票算法的记忆复杂性？

Question

根据地雷的理解，找到多数元素Boyer-Moore多数投票算法是O(1)，即它是常数，而不是与输入的大小成正比。那么为什么wiki链接提到对数空间{\显示方式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 (或类似的)单元格的数组。