teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

2

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

2015/09/15 03:45

投稿

eripong
eripong

スコア1546

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

1

誤字を修正した。

2015/09/15 03:45

投稿

eripong
eripong

スコア1546

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