私はこの宿題に約4時間取り組んでおり、これに関するいくつかの質問を理解することができましたが、これが何について話しているのかまだわかりません:
次のうち、正しいものと間違っているものはどれですか? また、その理由は?
(a) √n^5 ∈ O(n^2)
(b) √n log √n ∈ O(n)
(c) log(n^3) ∈ O(n log n)
(d) 2/n + 4/n^2 ∈ Θ(1/n)
(e) (log_2(n))^.5 ∈ Θ(log(n))
(f) min(700, n^2) ∈ Θ(1)
私の理解では、f(n)/g(n) を取り、それを n-> 無限大として極限に入れて解くことになっています..それが正しくないことを知っています。
どうすればいいですか？
どうもありがとう。
したがって、これを考えるには2つの方法があります。1つは、あなたが表現した方法、f(n)/g(n)、n->無限大として、値は0に近づきます。または、私が考える方法はより簡単です:
There is some pair of constants A and B such that A * g(n) + B > f(n) for all n.
これは、Big-O 表記法が表すものをより適切に表しています。つまり、ある関数の成長が別の関数の成長を消費するということです。これは、あなたの答えを確認するために、グラフ電卓を使用して簡単にチェックできるbig-o表記の表現でもあります:)。
通常、B の値は無視して、A*g(n) が f(n) よりも速く成長することを確認してください。Bは単なる形式です。