[B! programming][algorithm][order] manabouのブックマーク

manabou id:manabou

programmingとalgorithmとorderに関するmanabouのブックマーク (2)

競技プログラミングで頻出の「ダブリング」を解説する
競技プログラミングでは頻繁に出てくる「ダブリング」という手法について説明しようと思います。競プロをはじめて間もない人や、競プロ外の人に向けて書きたいと思います。最初に予防線を張っておきますが、内容が正しいかどうかは保証しません。繰り返し二乗法繰り返し二乗法という有名なアルゴリズムがあります。例えば、3の100億(10^10)乗を計算せよと言われた時に、 1回1回計算していたのでは時間がいくらあっても足りません。しかし繰り返し二乗法を使えば、log(100億)くらいの計算量で計算出来るようになります。具体的にどういう仕組みかを説明するためにより小さな場合として3の11乗を計算するとした時に、 3^11 = (3^8) x (3^2) x (3^1) と3^(2^k)の積に分解出来るならば、 11を1011と2進数で表した時の1の数分だけで計算が終わることになります。（a^bは
manabou 2020/05/12
programming

competitiveprogramming

algorithm

order
リンク
[初心者向け] プログラムの計算量を求める方法 - Qiita
はじめにこの記事では、プログラムの計算量を求める方法を説明します。プログラミングの初心者向けに、厳密さよりも分かりやすさを優先して説明していきます。サンプルコードについてこの記事のサンプルコードは、C言語（C99）で記述しています。計算量とは？計算量とは、「そのプログラムがどれくらい速いかを大雑把に表す指標」です。もう少し正確に言うと、「入力サイズの増加に対して、実行時間がどれくらいの割合で増加するかを表す指標」です。グラフによる計算量の表現計算量をグラフで表すと、以下のようになります。これは、**「入力サイズ $n$ が増加するにつれて、実行時間が $n$ に比例して増加する」**ということを表しています。別のグラフも見てみましょう。これは、**「入力サイズ $n$ が増加するにつれて、実行時間が $n^2$ に比例して増加する」**ということを表しています
manabou 2016/11/10
programming

order

algorithm

c
リンク
1