algorithm - アルゴリズムの分析記法確認

Question

これは宿題だと言っておきますが、一般的な宿題の助けを求めているわけではありません。質問の文言を確認したいだけです。質問は、私のアルゴリズムがグラフ内の頂点の数で線形であるべきだと述べています。私はその言葉遣いを見たことがありません。それは私の実行時間が O(|V|) であるべきだと言っているだけですか? もしそうなら、私は私の解決策を持っていると思います。

Answer 1

アルゴリズムの分析では、アルゴリズムは入力サイズの関数としての効率によって分類されます。

O(|V|)は、アルゴリズムがグラフ内のすべての頂点を調べる、つまり「触れる」必要があることを意味します。そうです、頂点数の線形は を意味しO(|V|)ます。

参考までに、大きなO、Ɵ、またはΩ; 2 本の縦棒はの数を意味します。また、一部のプルーフでは長さを表すためにも使用されます。