データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
37: デフォルトの名無しさん [sage] 2021/10/05(火) 00:11:45.95 ID:wQtjKuKa そのアルゴリズムの計算時間を f(n) とし、オーダーが O(g(n)) と表記される場合、定数cがあって、n がある程度大きくなれば常に f(n) <= c * g(n) が成り立つ。言い方を変えれば計算時間は最悪のケースでも c * g(n) を超えない g(n) が N (Nの1次式) なら計算時間は c * N を超えないし g(n) が N^2 (2次式) なら c * N^2 を超えない c はマシンのスペックや環境で変わるので具体的な数値は追求しない Nの入力サイズが10倍、100倍、...、1万倍となったときに計算時間がおおよそどのくらいのスピードで増えるか見積もれれば良い O(N) なら10倍、100倍、...、1万倍 O(N^2) なら100倍、1万倍、...、1億倍.. 詳しくはアルゴリズムの教科書か https://ja.wikipedia.org/wiki/ランダウの記号 http://mevius.5ch.net/test/read.cgi/tech/1580131715/37
39: デフォルトの名無しさん [sage] 2021/10/05(火) 03:31:33.71 ID:wQtjKuKa >>38 定義は同じ V個の頂点はそれぞれ1回キューに入れられて1回キューから取り出される E本の辺はある頂点から隣接する次の頂点を見つけるのに1度処理されるだけ 合わせてc0 * E + c1 * V の手間がかかるが、c0, c1 の大きい方を c として c0 * E + c1 * V <= c (E+V)、これは最悪でも計算量は c (E+V) を超えないことを意味し、E+V の部分が g(E+V) となる http://mevius.5ch.net/test/read.cgi/tech/1580131715/39
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.509s*