質問1：どのような状況下O(f(n)) = O(k f(n))で時間計算量分析の最も適切な形式でしょうか？
質問2：O表記法の数学的定義から作業してO(f(n)) = O(k f(n))、正の定数に対してそれをどのように示すkか？
最初の質問については、時間計算量の平均的なケースと最悪のケースの形式だと思います。私は正しいですか？そして、他に何を書くべきですか？
2番目の質問では、関数を数学的に定義する必要があると思います。k定数による乗算は、？の定義における任意の定数の値の再調整に対応するため、答えは次のようになりOますか？
私の見解: 最初のものについては、時間の複雑さの平均的なケースと最悪のケースの形だと思います。私は正しいですか？そして、他に何を書きますか？
いいえ！Big O表記は、平均的なケースまたは最悪のケースとは何の関係もありません。関数の成長の順序、特に、関数が別の関数と比較してどれだけ速く成長するかについてのみです。関数fはO(n)、平均的な場合とO(n^2)最悪の場合があります。これは、関数がその入力に応じて異なる動作をすることを意味するだけなので、2 つのケースを別々に考慮する必要があります。
質問 2 に関しては、質問の文言から、Big O の数学的定義から始める必要があることは明らかです。完全を期すために、それは次のとおりです。
正式な定義: f(n) = O(g(n)) は、すべての n ≥ k に対して 0 ≤ f(n) ≤ cg(n) となる正の定数 c および k があることを意味します。関数 f の c と k の値は固定である必要があり、n に依存してはなりません。
(ソースhttp://www.itl.nist.gov/div897/sqg/dads/HTML/bigOnotation.html )
したがって、この定義に基づいて、 を示す数学的証明を作成する必要がありますf(n) = O(k(n))。上記の定義O(g(n))を withに置き換えることから始めます。O(k*f(n))残りは非常に簡単です。
質問 1 は少しあいまいですが、質問 2 に対するあなたの答えは明らかに不足しています。質問には、「O表記の数学的定義から作業する」と書かれています。これは、インストラクターが数学的な定義を使用することを望んでいることを意味します。
f(x) = O(g(x)) if and only if limit [x -> a+] |f(x)/g(x)| < 無限大
そして彼は、g(x) = kf(x) をプラグインして、その不等式が成り立つことを証明してほしいと思っています。
あなたが投稿した一般的な議論は部分的な信用を得るかもしれませんが、それは数学ではなく推論であり、質問は数学を求めています.