O(N*logN)よりN=8の時、 O(N*logN) のOはオーダー記号と推察されますから 8*l

O(N*logN)よりN=8の時、

O(N*logN) のOはオーダー記号と推察されますから
8*log[2]8＝24
ではありますが
O(8*log[2]8)＝24
などとはできません。
と言われたのですが、
だとしたらO(N*logN)は何を表しているのでしょうか？O(N*logN)を調べましたがいまいちわかりません。仮にO(8*log[2]8)＝24ではなく、(8*log[2]8)＝24として、この24はN=8の時の図の何を表しているのでしょうか？

No.6 回答者： iruiru298 回答日時： 2022/04/08 08:07

＞だとしたらO(N*logN)は何を表しているのでしょうか？

以下の問題が解ければ、わかります。

問
「akitv」は文字式と推察されますから
行列a= 1 2　で、k=i=1のとき
　　　　3 4
aki = 1
ではありますが
akitvさんを1tvさんと呼んではダメ
と言われたのですが、
だとしたら「akitv」は何を表しているのでしょうか？

No.5 回答者： tknakamuri 回答日時： 2022/04/08 06:14

何で同じものが3つ？？？

教えてgooのバグ？

No.4 回答者： tknakamuri 回答日時： 2022/04/07 12:55

O(NlogN)

というのは
Nが充分大きい時
f(N)=ANlogN
で近似出来るということ。
Aは定数。

つまりNが充分大きければ
f(N)はNLogNにだいたい比例するということ。

ちなみに
N=1024から1024²に増やすと

f(1024)=p
とすれば、fが０(NlogN)なら

f(1024²)≒p×1024²Iog1024^2/(1024log1024)=2048p

fが０(N²)なら
f(1024²)≒p×(1024²)²÷1024^2=1050625p

この回答へのお礼

ありがとうございます。

O(N*logN) に関する解答として
>>FFTとは、直接的には何の関係もありません。FFTに必要な掛け算の回数が N→∞のとき大まかに N*logN に比例することを O(N*logN) と表現しているだけのことです。

なるほど、FFTに必要な掛け算の回数がNの値を入れた時のN*logNの式と単純に比例するため、O(N*logN) と表現しているだけだとわかりました。

お礼日時：2022/04/10 03:01

No.3 回答者： tknakamuri 回答日時： 2022/04/07 12:54

O(NlogN)

というのは
Nが充分大きい時
f(N)=ANlogN
で近似出来るということ。
Aは定数。

つまりNが充分大きければ
f(N)はNLogNにだいたい比例するということ。

ちなみに
N=1024から1024²に増やすと

f(1024)=p
とすれば、fが０(NlogN)なら

f(1024²)≒p×1024²Iog1024^2/(1024log1024)=2048p

fが０(N²)なら
f(1024²)≒p×(1024²)²÷1024^2=1050625p

No.2 回答者： tknakamuri 回答日時： 2022/04/07 12:53

O(NlogN)

というのは
Nが充分大きい時
f(N)=ANlogN
で近似出来るということ。
Aは定数。

つまりNが充分大きければ
f(N)はNLogNにだいたい比例するということ。

ちなみに
N=1024から1024²に増やすと

f(1024)=p
とすれば、fが０(NlogN)なら

f(1024²)≒p×1024²Iog1024^2/(1024log1024)=2048p

fが０(N²)なら
f(1024²)≒p×(1024²)²÷1024^2=1050625p

No.1 回答者： ありものがたり 回答日時： 2022/04/06 23:13

オーダー記号の変数に値を代入しちゃだめですよ。

O(N*logN) ってのは、 lim[N→∞] | f(N)/(N*logN) | が
無限大発散しないような関数 f(N) の総称です。
N が変数であることに意味があります。