単純なストリーミング アルゴリズムの go to の例のスペースの複雑さを判断したいと考えています。
n-1 個の異なる数字の順列を取得し、1 つの欠落した数字を検出する必要がある場合は、式 n (n + 1) / 2 を使用して 1 から n までのすべての数字の合計を計算し、次に入力された各数字を減算します。結果はあなたの不足している番号です。このアルゴリズムの空間複雑度は O(log n) であると述べているドイツ語のウィキペディアの記事を見つけました。( https://de.wikipedia.org/wiki/Datenstromalgorithmus )
私が理解していないのは、数値 n を格納するために必要なビット数は log2(n) です。わかりました..でも、合計を計算する必要があります。したがって、n (n + 1) / 2 は n よりも大きいため、log (n) よりも多くのスペースが必要ですよね?
誰かがこれで私を助けることができますか? 前もって感謝します！