たとえば、アルゴリズムの理論的な時間計算量は O(n 2 ) です。ただし、特定の、または現実的なケース (たとえば、Facebook のソーシャル グラフでは、各人が 200 人を超える親しい友人を持つことはできません) で実行される場合 (それが正しくないことはわかっていますが、仮定してみましょう)、その複雑さは線形 O になります。 (n) 理論的にはまだ O(n 2 ) ですが、入力のいくつかの特殊な特性によるものです。
現実的なケースでアルゴリズムの複雑さの正式な名前を見たことがあると思いますが、それが何であるかを正確に思い出せません。それは一種の「本当の複雑さ」または「現実的な複雑さ」または何かです。特別な名前があるかどうか知っている人はいますか？それとも、たまたま夢の中で何かを思い出しただけですか？:) テクニカル ライティングで必要です。ありがとう
アルゴリズムのパフォーマンスはデータ分布に大きく依存するため、このような種類の複雑さクラスに特別な名前はないと思います。ただし、実世界のデータの実行時間を見積もるアプローチには名前があります。それは平滑化分析と呼ばれます。
これに対する最良の答えは平均的なケースだと思います。平均は、入力の確率に対する加重平均として計算されるため、アルゴリズムa * n + bに入力I1とc * n^2 + d * n + e入力I2の複雑さがある場合、その平均複雑さは次のようになります。
AC = p * (a * n + b) + (1 - p) * (c * n^2 + d * n + e)
p入力の確率はですI1。実際の場合、入力がほぼ常に I1(つまりp = 1) である場合、平均的な複雑さは O(n) になります。学術的な証明は、入力の均一な分布を仮定する傾向があります (私の例では、すべての入力が同じ確率で発生p = 1/2します)。しかし、「現実の世界」でアルゴリズムの複雑さを研究するには、実際の発生確率を推定する必要があります。これにより、アルゴリズムの平均的な複雑さが変わる可能性があります (ただし、通常はそうではありません: この例では、 が であってp = 0.99999も、係数は変更されますが、平均的な複雑さは O(n^2) のままです)。
200 人を超える友人を持つ人は誰もいないと仮定すると、暗黙のうちに の確率を 0 に設定することになりますnb_friends > 200。これにより、最良のケースと最悪のケースが変わらなくても、平均複雑度が変わります。