「n = 10^10000 などの巨大なケースを考えると、c の保持などに必要な領域は n に依存するのでは」というご指摘かと思っていました。 (これに対する答えは「それはどうしようもないので許してください」です。) 唯一の過半数の候補 m が実際に過半数であるかの判定(二周目)はどうするのかということでしたか? 一周目終了時の m の値を残したまま c = 0 for v in votes: if v == m: c += 1 とすれば追加のメモリは不要です。 (100億個の数値を保持するのに80GB必要というのは、[0, 0, 0, ..., 0] という長さ100億の配列を作ったらということです。)
はい。(どの部分に対しておっしゃっていますか?この動画は全体的に過半数得票者が一人以下であることを前提としています。) vは「いま見ている票」を表す変数です。(別とはなんでしょうか?この動画のどの部分が誤っていますか?) 今回の証明に「行間」はほぼなく、さらに詳しく解説するのはなかなか難しいと思います。 英語になってしまいますが、en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm#Correctness に文章での証明があります(この動画の V が n となっています)。