algorithm - 改訂、二次時間

Question

ここにリビジョンプログラミングの質問を投稿できるかどうかはわかりませんが、いくつかのアルゴリズムのリビジョンで立ち往生しています

アルゴリズムが2次の場合、n ^ 2の数に比例して時間がかかりますか？

したがって、スライドがnレコードのほぼ1/2の二乗と言っている場合、これは（n ^ 2 * 0.5）と言っているのと同じです。

ありがとう

Answer 1

二次時間のアルゴリズムの複雑さは O(N^2) です。

その半分の場合、複雑さは O((N-1)^2) になります。この場合、N の値が大きいと実行時間に大きな影響を与えるため、-1 はそれ以上減りません。