上限が不明なときの問題解決法 - inamori’s diary
例えばProblem 60のような条件を満たす最小の解を求る問題を考えます。この問題は条件を満たすような解を小さい順に列挙するのが難しいです。しかし、上限を決めてその範囲で解が存在するかを含めて解くのは比較的簡単です。 このようなときは、適当に上限を決めるとよいです。例えば上限を1000と決めて、その範囲に解が無ければ、上限を2倍にして再び解を求めます。この方法は多くの場合にかなり有効です。上限を決めると問題がぐっと易しくなることはよくあります。また、直接解を求めるより時間がかかりそうですが、致命的にはかかりません。例えば、O(N)の問題のとき、解が8000で、いきなり上限を8000にして解を求めるたとき8秒かかったとします。ことのき、N = 1000から始めて倍々していくと、1 + 2 + 4 + 8 = 15秒かかります。まあ、倍くらいです。最悪の場合、N = 999から始めて倍々して
再帰呼び出しの計算量 - OKWAVE
再帰を用いた場合の計算量 nの階乗を再帰呼び出しを用いて計算する以下のプログラムの計算量はいくらになるのでしょうか？ 調べてみてもどこにも記述されていなくて困っています． int factorial(int n) { if(n > 0) return (n * factorial(n - 1)); else return (1); } また，できれば求め方も教えていただけると嬉しいです． nCrの計算 nCrの計算のプログラムを nCr=n!/(r!(n-r)!) を用いて再帰的関数を使って書いたのですが、もし nCr=n(n-1)(n-2)・・・(n-r+1)/r! であることを用いて、nからmまでの掛算を実現する2引数の関数を定義して、再帰的関数呼び出しを用いたnCrのプログラムを作成するとしたらどうなるでしょうか。 関数x!の定義は、関数の宣言をlong factorial(int
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計算
カジュアルなO記法 | 配電盤
O(1)というのはご機嫌に速いということ？ の続き。 アルゴリズム解析が教える計算量と、計算機で実際に計算する場合の計算時間の傾向が違うというのはよくあることで、経験の豊富な方が後者について詳しく解説することの意義は大きいと思います。（アーキテクチャに精通していない私には難しいです。） ただ、O記法とカジュアルなO記法は見た目の区別がつかないので（注釈を読み落とす危険もありますし）、後者については別な記法を導入した方が、潜在的な読者の混乱を未然に防げるのではないでしょうか。 「すでに2つの意味で使われているのだからしょうがない」ということもあるかもしれません。でも、世界をどちらの方向に動かしたいかと言えば、後者の意味ではO記法が使われない方向です。（自分が間違って使っていたら直したいです。） 補足 はい。それではdoubleの引数一つを取ってdoubleを返す関数のために、lookup t
O(1)というのはご機嫌に速いということ？ | 配電盤
「実際に起こりうる状況ではご機嫌に速い」という意味で「O(1)」と書くことがあるわけですが、誤解が生じるのでやめたほうがいいと思います。 たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック（程度）でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう。 もう少し厳密に言うと、精度に限りがあるのであれば、指数関数もO(1)でよい、ということです（ベキ乗はO(1)でOK?） もう少し厳密に言えば、O記法は極限の概念の上に成り立っているものなので、精度に限りがあるときには使いません。精度に限りがあるのなら、結果の入ったテーブルを使うことで、どんな関数でもご機嫌に速く計算できます。もっとも、テーブルを作るのに時間がかかるわけですが、 こうして一度出した結果を覚えておいて、あればそれを使うという方法はメモ化(m
Oyster Harbor | 計算量 (オーダーとO記法)
計算量とは 様々なアルゴリズムを考える上で重要な指標の一つが計算量 (computational complexity)です。 同じ結果が出力されるのなら、当然高速でメモリ消費量の少ないアルゴリズムを選択するべきです。 計算量は、時間計算量 (time complexity)と空間計算量 (space complexity)の2つに大別されます (他の指標もありますがここでは取り上げません)。 本記事では、おもに時間計算量を取り上げます。 しかしその前に、重要な概念であるO記法を知っておきましょう。 オーダ記法(ビッグオー記法, ランダウ記法) 計算量を比較するときに便利なのがO記法です。ここでは時間計算量を例にあげてO記法を説明します。 O記法は計算時間のうち、もっとも影響の大きい項のみで表記します。 たとえば、n個のデータを挿入ソートで並び替えることを考えます。 挿入ソートは平均すると
アルゴリズムの概要
第１項：アルゴリズムとは 第２項：アルゴリズムの性能 第３項：O(オー)記法 第４項：データ構造 ［１］アルゴリズムとは アルゴリズムとは、ある問題を解くための手順、すなわち、公式のことです。 もう少し厳密には、明確で有限個の手順を有限回繰り返す計算方法のことです。 ［ アルゴリズム ］ 明確に定義された有限個の規則の集まりであって、 有限回適用することによって問題を解くもの。 (JIS(日本工業規格)より) 明確な手順とはその通りの意味です。 第0部でも説明したように、コンピュータは明確な命令を必要とします。 「冷蔵庫からキムチを取ってこい」というのは不明確な命令であり、 「18度回転、182センチ前進、36度回転、腕を90度上昇・・・」は明確な命令です。 有限個の手順とは、少々不思議な表現です。 手順が無限になることは一般には考えづらいので、あまり気にしなくて
分類定理(master theorem) - LifeTimeException@hrk623
世界高校生プログラミング大会IOIも開催されるというので、今回はアルゴリズム解析ネタです。と言っても、昔のノートを引っ張り出してきただけっｹﾞﾌﾝｹﾞﾌﾝ・・・と、とりわけ、再帰プログラムの実行時間の計算に使われる分類定理についてです。 その前に アルゴリズム解析の際、表記には実行時間の成長を表す漸近記法を使います。よく知られているのは上界を表すO記法ですが、今回は上下界を表すΘ記法を使いますので、そちらも既に習得されている事を前提とします。（知らなくても特に問題はないかも？） ではでは、 再帰プログラムの実行時間は、大抵↑のような形になるので単純な計算で漸近実行時間は出てきません。 そこで 漸近実行時間の計算には、次のような3つの計算方法があります。 置き換え法(Substitution Method) 再帰木法(Recursion Tree Method) 分類法(Master The
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
DPの練習として良さそうなやつ - kyuridenamidaのチラ裏
いろいろなDPがありますが、これもまとめとくと良いと思ったので。僕はDPは得意ではないですが、それでもスキルアップに繋がったなあと感じた問題をピックアップしておきます。 DPかメモ化再帰か――ループの中で色々場合分けとかしなきゃいけなかったり、順序付けしにくかったりするＤＰは出来るならメモ化したほうがバグ減ったり実装楽だったりします。メモ化再帰は初期化ミスとかが無くて済むので。再帰が深くなりそうだったり、特殊なテクニック(ある区間をまとめて足したりする)とかする場合はやはりDPじゃないとだめですが、大体はメモ化再帰で代用が効きます。ではDP問の紹介。 (ネタバレ注意) 簡単な数え上げタイプ・Kannondou[☆]・A First Grader[★] 最長増加部分列タイプ( O(n log n)解法が存在するのでググったり蟻本とかを読むと良い。 )・ビルの飾りつけ(2007年度JOI春合宿
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
実践的アルゴリズム特論 10,11回目: 乱択アルゴリズム
確率と計算
クイックソートの動作と計算量解析
暗号基盤特論 #03 モーメントと偏差
計算機ソフトウェア 第六回
計算機ソフトウェア 第五回
サービス終了のお知らせ
Software Technology 2005
Aritalab:Lecture/Algorithm/BigO - Metabolomics.JP
漸近計算量理論
