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