タグ

関連タグで絞り込む (6)

タグの絞り込みを解除

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

  • 超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita

    4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N

    超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita

  • 競技プログラミングで頻出の「ダブリング」を解説する

    競技プログラミングでは頻繁に出てくる「ダブリング」という手法について説明しようと思います。 競プロをはじめて間もない人や、競プロ外の人に向けて書きたいと思います。 最初に予防線を張っておきますが、内容が正しいかどうかは保証しません。 繰り返し二乗法繰り返し二乗法という有名なアルゴリズムがあります。 例えば、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は

    競技プログラミングで頻出の「ダブリング」を解説する

  • 計算量について、償却/期待/平均など - noshi91のメモ

    本記事は皆様からのご指摘を募集しております 誤った記述があるかもしれません 概要 競技プログラミングをやっていると などの表記を見掛けることも多いでしょう *1。 それぞれについて、大雑把な意味をまとめました。 アルゴリズムの挙動の正確な把握は競技においても重要です。 以降、全て時間計算量に付いて議論します。 注: 本稿内で用いられる はほとんどが に置き換えられますが、 Big O notation と同時に説明すると混乱を招くと判断し、競技プログラミングにおいて常用されている を使用しています。 最良計算量 多くのアルゴリズムは、入力によって計算量が変化します *2。 例えば、ソートアルゴリズムには大まかに 通りの入力が存在します。 あり得る全ての入力のうちの計算量の最小値を最良計算量と呼び、 を付けて表記します。 線形探索は (最初に求める値が存在した場合) マージソートは 挿入ソー

  • 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita

    NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると

    計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita

  • [初心者向け] プログラムの計算量を求める方法 - Qiita

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

    [初心者向け] プログラムの計算量を求める方法 - Qiita
  • 1

お知らせ

もっと読む

公式Twitter

  • @HatenaBookmark

    リリース、障害情報などのサービスのお知らせ

  • @hatebu

    最新の人気エントリーの配信

はてなブックマーク

公式Twitter

はてなのサービス

  • App Storeからダウンロード
  • Google Playで手に入れよう
Copyright © 2005-2024 Hatena. All Rights Reserved.