time - Oの観点からの時間の複雑さ?

Question

入力のサイズが増加して時間が減少したときの時間計算量は?

Answer 1

それは、時間がどれだけ早く減少するかに依存します。たとえば、入力サイズを2倍にすると実行時間が半分になる場合、実行時間はになりますO(1/n)。

基本的に、これは、入力サイズを大きくすると実行時間も長くなる通常の場合と何ら変わりはありません。

もちろん、これは厳密に理論的なものです。実際には、入力サイズが無限大に近づくにつれて実行時間が減少し続けるアルゴリズムはあり得ないからです。

Answer 2

サイズが無限に近づくにつれて、時間の限界が何であれ。これは、「十分な大きさ」の入力の上限です。