2 つの時間複雑度を乗算する場合は、通常どおり乗算するだけであることを理解しています。たとえば、時間複雑度 を 時間複雑度でn log n乗算すると、時間複雑n度(n^2) log n
しかし、境界はどこに作用するのでしょうか? では、n log nが上限であり、n上限もある場合、それらの積はどのような範囲になるでしょうか? また、下限と上限と厳密にバインドされた他の組み合わせの場合はどうなるでしょうか? (たとえば、上限 x 厳密にバインド、上限 x 下限、厳密にバインド x 下限。)
助けてくれてありがとう。
これは純粋な数学の問題です。
f(x)がO(g(x))存在する場合にのみM、x0そのような|f(x)| <= M*|g(x)|すべてx > x0の これは、ほとんどの初歩的な複雑さの本で見られます。
f(x)であり、であるO(F(x))と仮定しg(x)ますO(G(x))。次に|f(x)| <= M_f * |F(x)|、すべてx > x0Fの|g(x)| <= M_g * |G(x)|ために、すべてのためにx > x0G。
|f(x) * g(x)| = |f(x)| * |g(x)| <= M_f * M_g * |F(x)| * |G(x)|すべてx > max(x0F, x0G)がそうf(x) * g(x)でO(F(x) * G(x))あり、複雑さが倍増します（ big-Oの定義に書き込んM = M_f * M_gでx0 = max(x0f, x0g)適用します）
では、n log n が上限であり、n も上限である場合、それらの積はどのような範囲になるでしょうか?
上限。正式な分析については、適切な教科書の回答を参照してください。これら 2 つの上限を乗算することの直感的な意味は、「それぞれ最大 n のコストで最大n lg n の操作を実行する必要がある場合、最大n ² lg nの作業を実行する」ということです。
上界 × 固縛
タイトな境界は上限と下限の両方であるため、これは上限です。
タイトバウンド×ローワーバウンド
...そして同じ理由で、これは下限です。
上限×下限
一般的なルールはありません。少なくとも n ² の操作を最大n回実行したとします。それはまったく仕事ではないかもしれませんし、指数関数的な量かもしれませんし、それ以上かもしれません。