回答編集履歴
2
Θ記法について追記した。
answer
CHANGED
|
@@ -1,9 +1,16 @@
|
|
|
1
|
-
Θ-記法はご存じでしょうか？
|
|
1
|
+
Θ-記法やΩ-記法はご存じでしょうか？
|
|
2
|
+
O-記法が上限を表すイメージで、Ω-記法が下限を表し、
|
|
3
|
+
Θ-記法はその両方を表すイメージです。
|
|
2
4
|
|
|
5
|
+
vc3000さんが参照しているWikipediaのページにも説明がありますし、
|
|
6
|
+
[計算量 - Security Akademeia](http://akademeia.info/index.php?%B7%D7%BB%BB%CE%CC)
|
|
7
|
+
[オーダー記法・その4 - あざらしとペンギンの問題](http://azapen6.hatenablog.com/entry/2013/02/15/235037)
|
|
8
|
+
等にも記述があります。
|
|
9
|
+
|
|
3
10
|
実際に、O(n*log n)と言った場合に、本当はΘ(n * log n)を意味していることが
|
|
4
11
|
多いように思います。
|
|
5
12
|
|
|
6
|
-
|
|
13
|
+
Wikipediaのページにも、以下の様な記述があります。
|
|
7
14
|
> もっと正確に漸近的に漸近的 tight bound であることを明示するならば Θ-記法を用いる。
|
|
8
15
|
|
|
9
16
|
以下の質問の回答にも、
|
1
誤字を修正した。
answer
CHANGED
|
@@ -1,14 +1,12 @@
|
|
|
1
1
|
Θ-記法はご存じでしょうか？
|
|
2
2
|
|
|
3
|
-
実際に、O(n*log n)と言った場合に、本当はΘ(n * log n)を意味していることが
|
|
3
|
+
実際に、O(n*log n)と言った場合に、本当はΘ(n * log n)を意味していることが
|
|
4
|
+
多いように思います。
|
|
4
5
|
|
|
5
|
-
vc3000さんが参照しているWikipediaのページにも、
|
|
6
|
+
vc3000さんが参照しているWikipediaのページにも、以下の様な記述があります。
|
|
6
7
|
> もっと正確に漸近的に漸近的 tight bound であることを明示するならば Θ-記法を用いる。
|
|
7
8
|
|
|
8
|
-
|
|
9
9
|
以下の質問の回答にも、
|
|
10
10
|
[What is the difference between Θ(n) and O(n)?](http://stackoverflow.com/questions/471199/what-is-the-difference-between-Θn-and-on)
|
|
11
|
-
|
|
12
11
|
> when people talk about O(g(n)) they actually mean Θ(g(n)) but technically, there is a difference.
|
|
13
|
-
|
|
14
12
|
とあります。
|