私は主に時間の複雑さに関する試験のために勉強しています。これらの 4 つの質問を解決しているときに問題が発生しました。
1) アルゴリズムの時間計算量が theta(n^2) であることを証明した場合、すべての入力に対して O(n) の時間計算が必要になる可能性はありますか?
2) アルゴリズムの時間計算量が theta(n^2) であることを証明した場合、一部の入力に対してO (n) の時間計算が必要になる可能性はありますか?
3) アルゴリズムの時間計算量が O(n^2) であることを証明した場合、一部の入力に対してO (n) の時間計算が必要になる可能性はありますか?
4) アルゴリズムの時間計算量が O(n^2) であることを証明した場合、すべての入力に対して O(n) の時間計算が必要になる可能性はありますか?
そのような質問に答える方法を誰か教えてください。彼らが「すべて」または「一部」の入力を求めたとき、私はほとんど混乱しています。ありがとう