回答編集履歴

2

Θ記法について追記した。

2015/09/15 03:45

投稿

eripong
eripong

スコア1546

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
- vc3000さんが参照しているWikipediaのページにも、以下の様な記述があります。
25
+ Wikipediaのページにも、以下の様な記述があります。
12
26
 
13
27
  > もっと正確に漸近的に漸近的 tight bound であることを明示するならば Θ-記法を用いる。
14
28
 

1

誤字を修正した。

2015/09/15 03:45

投稿

eripong
eripong

スコア1546

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のページにも、いかn
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
  とあります。