O(1)、O(n)、O(n*n)メモリの意味は何ですか? [重複] 質問する

xmoex が言ったように:

o(1) は一定のメモリ使用量を構成します。したがって、入力量は重要ではありません。

o(n) は線形のメモリ使用量を構成します。したがって、入力が増えると、メモリも線形に増えます。

o(n*n) はメモリ使用量の 2 乗を構成します。つまり、入力が増えるとメモリも 2 乗で増えます (平均で x^2)。

ほとんどの場合、メモリの複雑さのこの測定は、時間の複雑さの測定とは完全に独立しています。コンピュータ アルゴリズムの場合、アルゴリズムの品質を決定するには、アルゴリズムがこれらの複雑さの両方をどのように管理するかを知ることが重要です。ただし、両方を個別に計算する必要があります。問題の使用例や状況によっては、一方が他方よりも重要になる場合があります。