- データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
65 ：デフォルトの名無しさん[sage]：2016/09/24(土) 09:32:41.92 ID:n5/uj8Su - 64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
68 ：デフォルトの名無しさん[sage]：2016/09/24(土) 09:55:26.18 ID:n5/uj8Su - >>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。
まあ、原理は単純なアルゴリズムです
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
71 ：デフォルトの名無しさん[sage]：2016/09/24(土) 11:09:23.58 ID:n5/uj8Su - >>69
>>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます
|
|