取引ガイド

フィボナッチ数列の計算量について

フィボナッチ数列の計算量について
大石ゆかり

フィボナッチ数列の計算量について

時代の課題と社会の要請に応えた専門的知識と技能/Expert knowledge and skills to address the issues of the age and the demands of society

本計画では修得範囲を明示するものであり、実習、演習ならびにテストの与え方は、進度により前後することがある。なお、個人の予習として、①事前に指定された範囲のテキストを読んでおき、②分からないことについて事前に意識しておくことで、講義に臨むことが効果的である。また、復習として、③理解しにくかったことをコンピュータ操作を通じて納得すること、④プログラミングを自らすること、⑤次回の授業の準備をすることで、受講生の記憶に定着することを期待する。また、 予習・復習に各回あたり4時間程度の自己学習 を想定している.

第Ⅰ部:アルゴリズムはなぜ重要か
1. オリエンテーション(シラバス記載事項の確認を含む)、繰り返し計算と解析解、計算量、データ構造、Python の導入
【予習】自らの計算機環境にPythonをインストールし、四則演算などの簡単な処理ができることを確認する.
2. アルゴリズムを表現する様々な方法、Python の文法、アルゴリズムの表現(図、言葉、フローチャート、疑似コード)、モデル化 フィボナッチ数列の計算量について
【予習】教科書の例題を読むとともにPythonのプログラムをあらかじめ動かし、疑問点を整理する.
3. ソートとは、選択ソート、最悪計算量、最良計算量、平均計算量
【予習】教科書のソート説明部分を読み、例えば、を昇順に並べる手順を考える.

第Ⅱ部:アルゴリズムを設計するには
4. 挿入ソート、バケットソート
【予習】選択ソートも含め、同じソートでも何が違うのかについて比較しておく.
5. バブルソート、バブルソートの改良版 フィボナッチ数列の計算量について
【予習】新たに加わったソートも含め、それらの違いについて比較する.
6. 分割統治法、動的計画法、フィボナッチ数列
【予習】教科書の例題を読んでおき、疑問点を整理する.

第Ⅲ部:アルゴリズム設計法を応用するには
7. フラクタル図形、「ハノイの塔」問題、最短経路問題
【予習】ハノイの塔の実際に動かすディスクの枚数として3, 4, 5の3ケースについて、紙の上で解いてみる.
8. マージソート
【予習】既に学んだソートの方法とマージソートの違いについて整理しておく.
9. クイックソート、整列の安定性
【予習】クイックソートとマージソートとの違いについて整理しておく.

第Ⅳ部:データ構造はなぜ重要か
10. 探索、線形探索、二分探索、木、二分木、二分探索木、グラフ
【予習】教科書を読み、二分木について疑問点を整理しておく.
11. スタック、キュー、深さ優先探索(バックトラック)、幅優先探索、リングバッファ
【予習】各種データ構造の違いについて疑問点を整理しておく.
12. 全順序集合、優先度つきキュー、ヒープ、ヒープソート
【予習】二分木などのツリー構造を用いてソートを実施するにはどんなことがありうるか考えを整理しておく.

第Ⅴ部:アルゴリズムとデータ構造を設計するには
13. 貪欲法、釣り銭のアルゴリズム、最良優先探索、最短路問題、ダイクストラ法
【予習】教科書の例題にある経路問題について、自分なりのやり方の考えを整理しておく. フィボナッチ数列の計算量について
14. 力まかせ探索、ミニマックス法、分岐限定法、枝刈り
0-1ナップサック問題、分割ナップサック問題
最後に、本講義全体に関わる問題形式のまとめとそれに対する質疑応答の時間を設ける。
【予習】教科書の例題にあるナップザック問題について、自分なりに解き疑問点を整理しておく.また、講義全体についても疑問点を整理し、講義中に質疑するための準備をする.

1. 大学の授業支援システム(dotCampus)を通じて情報を提供するので、チェックを欠かさず行うこと。
2. 授業中のトイレ等の途中出入りは原則できない。事前に体調管理・時間的余裕をもって行動すること。 フィボナッチ数列の計算量について
3. 指定使用書を持参すること。
4. PCを活用して講義の理解に努めること。
5. 個人的に、神奈川大学のメールアドレス([email protected]など)に連絡をとることがあるので、日頃必ずチェックするメールアドレス(携帯電話メールなど)への転送設定などし、伝達漏れが起きないようにすること。

以下の時間帯と場所を設定する。
・森田:月曜日12:40~13:20、23号館4F411号室または412号室。
・西澤:木曜日12:40~14:00、6号館4F418号室。
なお、長時間に及びそうな相談の場合は、Email等で別の時間を予約の上、来訪すること。

動的計画法がわかる!ダイクストラ法の実装(フィボナッチ数列の計算量について Python)や問題への適用手順

今回は,Viterbiアルゴリズムの解説(【技術解説】HMMに基づいたViterbiアルゴリズムによる解推定手法(例題つき))をした際に登場した 動的計画法 について,その解説と,簡単な例を用いたプログラム(Python)での実装例を紹介する.また,問題文から動的計画法を用いて問題を解決する際のプロセス(フィボナッチ数列の計算量について 漸化式の作成方法等)についても触れながら,具体的な応用方法について確認する.まずは,動的計画法とはどういうものなのか,概要を確認しよう.

動的計画法(DP;Dynamic Programming)とは

動的計画法の概要

動的計画法とは そのままでは解けないような大きな問題を複数の小さな問題(部分問題と呼ぶ)に分解し,部分問題を解くことで元の大きな問題を解く手法の総称 である.動的計画法を用いることで多項式時間で解くことができない一部の問題について,類似多項式時間で最適解を求めることができる(後ほど解説).問題のある手法が動的計画法であるかどうかを判断する際には,分割統治法メモ化の2つを満たしているかどうかが条件となる.はじめに,多項式時間分割統治法メモ化について理解しよう.

多項式時間,多項式時間アルゴリズムとは

多項式時間とは多項式で表される 計算時間 を指し,多項式時間アルゴリズムとは 入力サイズ(長さや個数)をnとした時,計算時間(ステップ数)の上界がnの多項式時間で表現できるアルゴリズム を指す.例えば,九九を計算するアルゴリズムの計算時間は9×9で計算できる.これをn×nに拡張した場合の計算時間のオーダーは”O”記法を用いてO(n 2 )と表される.これは,この計算時間の上界がn 2 で表現できることを指しているため,n×nの掛け算を計算するアルゴリズムは多項式時間アルゴリズムであるといえる.

しかし,多項式時間で解けない問題も存在する.例えば,今回の解説でも取り上げる最短経路問題は多項式時間で解くことはできない.図のような重み付き経路について,STARTからGOALに最短コストで到着する経路を求める問題を考えてみよう.

最短経路を求めるためには全経路の組み合わせを考慮した上でSTARTからGOALまでのコストを計算し,コストが最小の経路を選択する必要がある.このような問題では入力サイズが増えていく毎に経路パターンが指数的に増加していくため,全経路のコストを計算する手法は現実的ではない.しかし,動的計画法を使用することで,最短経路問題のような多項式時間で解けない問題の最適解を解ける場合がある.その計算時に使用するのが分割統治法メモ化という2つの手法である.

分割統治法とは

分割統治法とは 対象の問題を部分問題に分割する手法 を指す.では,先ほど挙げた最短経路問題を部分問題に分解してみよう.今回の例では,まずSTARTからENDの全経路を考えるのではなく,ある時点から進むことができる経路のみを考えるというアプローチをとることとする.すると,初めの経路はSTARTからa, b, c, dの4本のみ考えればよいことになる.最短経路問題を解くことを考えると,ここではSTARTから最も低いコストで遷移できるSTART→bを選択しよう.

次は,bから進むことができる経路のみを考え,ここでも最もコストが低い経路を選択する.今回の例ではb→gを選択することになる.

このように全経路を考える問題をある時点から進むことができる経路のみを考える問題(部分問題)に分割するような手法を分割統治法と呼ぶ.

メモ化とは

メモ化とは 計算結果をメモリ上などに保持し,あとから再利用する手法 を指す.メモ化の例として,フィボナッチ数列を計算する問題を考えてみよう.フィボナッチ数列についての説明は割愛する.フィボナッチ数列をPythonで計算する場合,通常は以下のようなコードになる.

CulcFibonacci.py

しかし,このコードではn=10を計算するために,再度n=9~1までの計算をする必要があり,計算時間はO(α n )(α:実数)となるため,nが大きくなるにつれて計算量が指数的に増加していく.

このコードをメモ化によって最適化する際には,複数回計算される点が重要となる.メモ化をするためにメモ化テーブルを作成し,1度計算した値はメモ化テーブルに保持してみよう.

CulcFibonacciMemo.py

メモ化の最大のメリットは計算量が減ることで計算時間を削減できることである.このソースコードでは一度計算したフィボナッチ数をリストに格納しておき,あとで再利用することで計算量を減らす試みがされている.実際に著者のPCで40番目のフィボナッチ数を計算した際の計算時間を比較すると,前者のメモ化なしプログラムでは101.9秒だったのに対して,後者のメモ化ありプログラムでは 0.2秒 と大幅に計算時間が短縮されていた.動的計画法では部分問題を再帰的に計算するため,このメモ化による最適化が大きな意味を持つ.

それでは,動的計画法の概要についてはここまでとし,次は最短経路問題を動的計画法の一種である ダイクストラ法 で解いてみよう.

例題:最短経路問題をダイクストラ法で解く(フィボナッチ数列の計算量について Python実装)

ダイクストラ法は 最短経路問題を効率よく解く手法 である.今回は『分割統治法とは』の項で使用したものより簡単な以下のグラフを用いて計算手順を確認しよう.

ダイクストラ法の計算手順

まずSTARTから伸びるエッジでつながるノード(a, b, c)についてSTARTからの最短経路を求める.今回の例ではSTARTから伸びるエッジでつながるノードのうち,ノードbが最小コスト3で遷移可能であることがわかる.また,STARTから別のノードを経由してbにたどり着いても,負のコストがない限り,他ノード経由の経路はSTART→bの経路よりコストが高くなることがわかるだろう.そのためSTARTからノードbへの最短経路はSTART→bと確定できる.

次に先ほど確定したノードbからたどり着けるノードa, c, GOALについて最小コストを求める.ここでノードbにたどり着くまでのコストは3で確定していることに注意してほしい.また,ここで注目すべきはノードaとノードcには,ノードb以外にSTARTからもエッジが伸びていることである.そのためSTARTから各ノードへの最短経路は STARTからの最短距離とノードbからの最短経路のうち,コストが低い経路 となる.これらを踏まえて計算すると,先ほど確定したノードbから各ノード(a, c, GOAL)へ遷移する最小コストはノードaが4,ノードcが5,ノードGOALが8となる.ここから,先ほどと同様に最小コストで遷移できるノードを確定するとノードaが確定される.

手順に従い,次に先ほど確定したノードaについて遷移可能なノードから最小コストのノードを選ぶ.しかし,ノードaから遷移可能なノードSTART, bはどちらもすでに最小コストが確定している.そのため,先ほどノードaの次に小さいコストで遷移可能であったノードcを確定としノードcからたどり着けるノード(GOALのみ)について最小コストを求める.お分かりのとおり,STARTからノードcへの最小コストは5と確定しているため,ノードGOALへ遷移するコストは6となり,ノードGOALが確定する.

ノードGOALが確定した時点で,ダイクストラ法の計算は終了である.最後にノードSTARTからノードGOALへの最短経路(最小コストで遷移可能な経路)を考えよう.これまでの計算でノードGOALにたどり着く経路は「START→b→GOAL(コスト8)」と「START→b→c→GOAL(コスト6)」の2通りがあることがわかっている.もうお分かりのとおり ノードSTARTからノードGOALへの最短経路は「START→b→c→GOAL(コスト6)」 となる.

Pythonで再帰的な関数を利用してフィボナッチ数列を実装する方法を現役エンジニアが解説【初心者向け】

田島悠介

大石ゆかり

田島悠介

大石ゆかり

フィボナッチ数列とは

再帰的な関数を利用してフィボナッチ数列を実装してみよう

「スクールは高いから独学で成功する」という気持ちの方は多いと思います。
もちろんその方が金額は低く抑えられるでしょう。
ただ 独学には向き不向きがあり、実はスクールが向いている人も大勢います。

そんな方のために参考として、 テックアカデミー卒業生がスクールを選んだ理由 をご紹介します。

  • ・困って挫折しそうなときに、質問や相談できる相手がいる環境で学んでいきたいなと思った
  • ・わかった気になっているだけだったので、自分を追い込む環境に置いた方がいいと感じた
  • ・スクールのカリキュラムで市場に求められるスキルを学ぶべきと思った

少しでも当てはまる部分があれば、 スクールが向いているかもしれません。
お試しのつもりで、まずは一度 無料相談 に参加してみませんか?

現役エンジニア・デザイナーに何でも気軽に相談できる30分 を すべて無料で できます。
無理な勧誘は一切ない ので、お気軽にご参加ください。

執筆してくれたメンター

得意言語はPython, HTML, CSSで、機械学習やデータ分析、スクレイピングなどが得意。

大石ゆかり

田島悠介

大石ゆかり

初心者・未経験でもできる。まずはテックアカデミーに相談しよう

  • ・調べてもほしい情報が見つからない
  • ・独学のスキルが実際の業務で通用するのか不安
  • ・目標への学習プランがわからず、迷子になりそう

テックアカデミーでは、このような フィボナッチ数列の計算量について 学習に不安を抱えている方へ、現役エンジニア講師とマンツーマンで相談できる機会を無料で提供 しています。
30分間、オンラインでどんなことでも質問し放題です。

「受けてよかった」と感じていただけるよう 厳しい試験を通過した講師 があなたの相談に真摯に向き合います。

「ただ気になることを相談したい」
「漠然としているがプロの話を聞いてみたい」
こんな気持ちでも大丈夫です。

無理な勧誘は一切ありません ので、まずはお気軽にご参加ください。
※体験用のカリキュラムも無料で配布いたします。(1週間限定)

記事を検索

関連するキーワード

関連する記事

Pythonのformat関数で出力文字列をセンタリングする方法を現役エンジニアが解説【初心者向け】

Pythonのダブルクォーテーション3つで囲まれたコメントについて現役エンジニアが解説【初心者向け】

Pythonで現在時刻を取得する方法を現役エンジニアが解説【初心者向け】

Pythonで配列のデータの平均を求める方法を現役エンジニアが解説【初心者向け】

Pythonのqueueとdequeについて現役エンジニアが解説【初心者向け】

Pythonのsyslogモジュールでログ出力する方法を現役エンジニアが解説【初心者向け】

あわせてよく読まれている記事

JavaScriptで再帰処理を行う方法を現役エンジニアが解説【初心者向け】

JavaScriptで再帰処理を行う方法について、TechAcademyのメンター(現役エンジニア)が実際のコードを使って初心者向けに解説します。 JavaScriptについてそもそもよく分からないという方は、JavaScriptとは何なのか解説した記事をまずご覧ください。 なお本記事は、TechAcademyのオンラインブートキャンプ、JavaScript/jQuery講座の内容をもとにしています。 フィボナッチ数列の計算量について 田島悠介 今回は、JavaScriptに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 JavaScriptで再帰処理を行う方法について詳しく説明していくね! 大石ゆかり お願いします! 再帰処理とは 再帰処理とは、ある処理について、その処理の中で自身を呼び出すような処理のことを言います。 再帰処理のサンプルと解説 再帰処理のサンプルとしてフィボナッチ数列を取り上げてみます。フィボナッチ数列から引数で指定した位置の数字を取得する関数を考えます。まず、フィボナッチ数列がどのような数列であったかと言うと、 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . ] JavaScriptの配列に見立てて最初の0を0番目と考えることにします。例えば、6番目の8という値は、4番目の3と5番目の5を足した数になっています。 なので、次のような式が成り立ちます。 F(0) = 0 (n = 0) F(1) = 1 (フィボナッチ数列の計算量について n = 1) F(n) = F(n-2) + F(n-1) (n >= 2) これを、JavaScriptの関数として記述してみます。 const f = n => n < 2 ? n : f(n-2) + f(n-1) 試しにコンソールに出力して確認しましょう。 for (let i = 0 ; i <= 10 ; i++) < console.log(f(i)) >関数fは、その処理の中で自身である関数fを呼び出しています。つまり、この関数は再帰処理をしています。 [PR]

JavaScriptでDOMを再帰的に操作する方法を現役エンジニアが解説【初心者向け】

Pythonのlinspaceメソッドの使い方を現役エンジニアが解説【初心者向け】

Pythonのlinspaceメソッドの使い方について解説します。linspaceを使うことでコード量を減らし読みやすいプログラムを組むことができるようになります。ぜひ参考にしてみてください。 そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。 なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。 田島悠介 今回は、Pythonに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 Pythonのlinspaceメソッドの使い方について詳しく説明していくね! 大石ゆかり お願いします! linspace()とは? まず、linspace()について説明します。 linspace()はPythonのライブラリNumpyの関数で、 数列を作りたいときなどによく使われる便利な関数です。数列を作りたいときというのは、関数のグラフの描画をするときなどが挙げられます。 linspace()で作ることのできる数列には次のようなものがあります。 array(フィボナッチ数列の計算量について フィボナッチ数列の計算量について [ 0., 3., 6., 9., 12., 15., 18., 21., 24., 27., 30.]) これは、0から始まって30まで3ずつ増えていく数列です。このような数列は同じNumpyライブラリのarange()関数を使って作ることもできます。 しかし、linspace()関数を使うことで少ないコードで書くことできるので、コードを書く方にも読む方にも利点があります。 NumPyのインストール linspace()関数を使う前に、まずはNumpyをインストールしましょう。基本的には、Pythonのパッケージ管理ツールであるpipコマンドを使えば、 pip install numpy を実行するだけでインストールができるはずです。Numpyがインストールできていることを調べます。 pip list を実行すると、これまでにインストールしたパッケージが確認できます。リストの中にnumpyが確認できたら大丈夫です。 [PR] Pythonで挫折しない学習方法を動画で公開中linspace()の使い方 linspace()は、公式のドキュメントで、 numpy.linspace(start, stop, num フィボナッチ数列の計算量について = 50, endpoint = True, retstep = False, dtype = None) と書かれているように引数は6つありますが、linspace()は基本的に3つの引数を指定して使います。実用上知っておくべきなのは、start, stop, numの3つです。 startは数列の開始点を指定する stopは数列の終了点を指定する numは数列の要素の数を指定する ものです。 他の引数については、endpointは数列の終了点を要素に含めるかどうかを、retstepは数列の公差を表示するかどうかを、dtypeは数列の各要素のデータ型を、それぞれ決めるものです。 これらに関しては、ドキュメントにも詳しく説明されているので、必要に応じて目を通しておくと良いでしょう。 linspace()を実行すると数列のndarrayが出力されます。retstepがTrueになっている場合は、数列の公差も出力されます。 linspace()を利用して数列を生成してみよう それでは実際にlinspace()を使ってみましょう。まずは、 import numpy as np を実行してNumpyをインストールします。そして、まずは、00から始まって30まで3ずつ増えていく数列を出力しましょう。 print(np.linsapce(0 ,30, 11)) これを実行すると、 [ 0. 3. 6. 9. 12. 15. 18. 21. 24. 27. 30.] と表示されると思います。retstepをTrueにして、 print(np.フィボナッチ数列の計算量について linsapce(0 ,30, 11), retstep=True) を実行すると (array([ 0.,

Pythonで再帰関数を作る方法【初心者向け】

Pythonで再帰関数を作る方法について解説します。 そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。 なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。 田島悠介 今回は、Pythonに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 再帰関数を作る方法について詳しく説明していくね! 大石ゆかり お願いします! 再帰関数とは 再帰関数とはプログラミングの手法の1つで、プログラムの中に自分自身の呼び出しが含まれているものを言います。 再帰関数は、繰り返し関数と同様に、同様な処理を複数回行う場合に利用されますが、より複雑な問題を簡単な問題に置き換えて処理できると言われています。再帰関数は以下のような場面で利用されています。 データ処理 複数のデータをソートしたり、繰り返し処理を行う場合、データ構造によっては再帰関数を使うと効率的な場合があります。 再帰データ型 フィボナッチ数列の計算量について 複雑な問題の解決 よく例題としてあげられるのが「ハノイの塔」の問題です。一定のルールに従い、毎回状態が変わる処理に対して、再帰関数を使うと簡単な問題に置き換えて処理することができます。 ハノイの塔 構文解析(自然言語処理) 自然言語処理において、文章を単語に分解する処理を、再帰関数を用いて行う場合があります。自然言語処理については以下の記事も参考にしてください。 自然言語処理とは!仕組みやライブラリを解説 余談ですが、再帰的表現はプログラミングで古くから用いられており、コンピュータ関連の用語にもしばし登場します。例えば「Linux」は「Linux is not unix」の略語であり、自分自身がもととなる文章に含まれています。 再帰的頭字語 Pythonで再帰関数を作る方法 Python ではユーザー定義関数を利用して再帰関数を作成することができます。 def myfunc(x): if フィボナッチ数列の計算量について 終了条件: return x // 何かの処理を行う myfunc(x) 注意点は以下の通りです。 必ず終了条件を入れましょう。終了条件が無いと永久に再帰呼び出しを行い、処理が終わらなくなってしまいます。 再帰呼び出しを行う際の引数に注意しましょう。こちらも状態が変わらないままだと、終了条件の判定が正しく行えません フィボナッチ数列の計算量について プログラムの内容が複雑だと感じたら、再帰関数以外で実現出来ないか考えてみましょう。再帰関数はシンプルに記述できる反面、処理を追いづらくバグを発見しづらいという面もあります。 [PR] Pythonで挫折しない学習方法を動画で公開中実際に書いてみよう 今回のサンプルプログラムでは、1からnの整数の和を返すプログラムを、再帰関数を使った場合と使わない場合で確認します。はじめに再帰関数を使わない場合です。 def sum(n): ret = フィボナッチ数列の計算量について 0 for i in range(1, n + 1): フィボナッチ数列の計算量について ret += i return ret s = sum(100) print("1から100の合計は", s,

Pythonで等差数列を作る方法【初心者向け】

Pythonで等差数列を作る方法について解説します。 そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。 なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。 田島悠介 今回は、Pythonに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 Pythonで等差数列を作る方法について詳しく説明していくね! 大石ゆかり お願いします! 等差数列を作る方法 等差数列とは、隣の値(項)との差が同じ数列のことです。例えば以下のような数列です。 10, 20, 30, 40, 50, . Python で等差数列を作成する方法はいくつかあります。 rangeを使う方法 range(開始, 終了, ステップ) 開始から終了-1までの範囲で、ステップの差で数列を作成します。戻り値は range 型となります。 NumPy の arange を使う方法 numpy.arange(開始, 終了, ステップ, dtype) こちらも同様です。開始とステップ、dtypeは省略できます。dtypeは数列の要素の型を指定します。初期値はNone(開始や終了の型に合わせる)です。 NumPy フィボナッチ数列の計算量について の linspace を使う方法 numpy.linspace(開始, 終了, 分割数, endpoint = True, retstep = False, dtype = None) こちらは上記とは考え方が異なり、開始から終了までの範囲を分割数で分割した数列を返します。終了も含みます。開始と終了は必須です。その他のオプションは省略可能です。 オプション 説明 既定値 分割数 出来上がる数列の要素数 50 endpoint 終了を要素に含むか True フィボナッチ数列の計算量について retstep Trueにすると公差を表示 False dtype 数列の要素の型 None(float型になる) 実際に書いてみよう 今回は上記の3つの方法における等差数列の書き方を確認します。確認しやすいよう、結果は NumPy 配列型で表示することとします。プログラムは Python インタプリタで入力していきます。事前に Python と NumPy ライブラリをインストールする必要があります。はじめに必要なライブラリをインポートしておきましょう。 import numpy as np 最初は range を使う方法です。 np.array(range(10, 151, 10)) 実行結果は以下のようになります。 array([ 10, 20, 30, 40, 50,

PHPで再帰処理を実装する方法を現役エンジニアが解説【初心者向け】

今回は、PHPで再帰処理を実装する方法について、TechAcademyのメンター(現役エンジニア)が実際のコードを使用して初心者向けに解説します。 PHPについてそもそもよく分からないという方は、PHPとは何なのか解説した記事を読むとさらに理解が深まるでしょう。 なお本記事は、TechAcademyのオンラインブートキャンプPHP/Laravel講座の内容をもとに紹介しています。 田島悠介 今回は、PHPに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 PHPで再帰処理を実装する方法について詳しく説明していくね! 大石ゆかり お願いします! この記事ではPHPで再起処理を実装する方法について解説します。 目次 再帰とは 再帰関数の使い方 再帰処理の例 実際に書いてみよう まとめ 再帰とは 再帰処理とは、関数がメソッドの中で自分自身を呼び出す処理のことです。 再帰処理は自分自身を呼び出すため適切な終了処理をしない限り無限ループになってしまう点に注意する必要があります。 [PR] Pythonで挫折しない学習方法を動画で公開中再帰関数の使い方 再帰関数は関数の中に自分自身を呼び出すことをいいます。ただそのままだと無限に自分自身を呼び出し続けるため終了条件が必要になります。 再帰関数は以下のように書きます。 フィボナッチ数列の計算量について フィボナッチ数列の計算量について function 関数名(引数) < if (終了条件) < return 戻り値; >else < 関数名(引数); return 戻り値; >> 自分自身を再度呼ぶ際に同じ引数を設定すると無限ループになるため引数を別の値に変えるようにする必要があります。 再帰処理の例 再帰処理の例として階乗の計算について紹介します。 階乗とは数学の計算方法の1つで4!や5!のように「数字!」と書きます。1から数字までの整数を掛け合わせた値を得ることができます。 6!だと以下のような計算になります。 6! = 1 * フィボナッチ数列の計算量について 2 * 3 * 4 * 5 * 6; ただこの計算はこのような理解もできます。 6! = 5! * 6; 6! = (4! * フィボナッチ数列の計算量について 5) * 6 6! = ((3! * 4) * 5) *

フィボナッチヒープ フィボナッチヒープの概要

フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。つまり最小のキーは常に何れかの木のルートにある。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木は規定された形を特に持っておらず、極端な場合はヒープ中の n 個の要素が全て別々の(n 個の)木に属しているかもしれないし、深さ n の一つの木に属しているかもしれない。この柔軟さによって、ある種の操作を後回しにするなど「怠惰な」処理方法が許される。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを連結するだけで良いし、「キーの減算」操作の過程ではあるノードが親から切り離されて新しい木を作る場合がある。

しかしながら、処理時間を抑えるためには、何らかの時点でヒープにある種の秩序を導入しなければならない。特に、ノードの次数(=ノードが直接持つ子の数)はかなり小さく抑えられる:個々のノードの次数はたかだか O(log n) であり、かつ、次数 k のノードが持つサブツリーの大きさは少なくとも Fk + 2 である(ここで Fk は k 番目のフィボナッチ数)。これを守るために、ルートでないノードからはたかだか一つの子しか切り取れないという規約を作る。二つ目の子を切り取る場合は、そのノード自身も親から切り取って新しい木のルートにする。木全体の数は「最小値の削除」操作によって木同士を繋ぐことで減少する。

P o t e n t i a l = t + 2 m

しかしながら最小値拡大操作を完了するには、最小値を持つルートノードへのポインタを更新する必要がある。不幸にもn個までのルートノードをチェックする必要があるかもしれない。二番目のフェーズでは、同じ次数のルートノードを一緒につなげてルートノードの数を減らす。uとvという二つの同じ次数のルートノードがあった場合、一方を子にしてよりキー値が小さいもう一方をルートのままにしておく。そのルートの次数は一つ増える。この操作をすべてのルートが異なる次数になるまで繰り返し行う。同じ次数の木を効率的に検索するために、O(log n)の長さを持つ配列を用意し、それぞれの深さのあるルートへのポインタを保持するようにする。2番目に同じ深さのルートが見つかったならば、その二つの木を結合して配列の内蔵を更新する。二番目のフェーズ開始時のルートの数がmとすると、実実行時間はO(log n + m)になる。最後に、高々O(log n)個のルートになる(それぞれのルートは異なる次数になっている)。それゆえにポテンシャルは少なくともm - O(log n)減り償却時間はO(log n)になる。

3番目のフェーズではルートとして残っているものをチェックして最小値を検索する。これにはO(log n)の時間がかかりポテンシャルは変化しない。最小値拡大操作の全体の償却時間はO(フィボナッチ数列の計算量について log n)になる。

問題解決力を鍛える!アルゴリズムとデータ構造

問題解決力を鍛える!アルゴリズムとデータ構造

11章 データ構造(4):Union-Find
11.1 Union-Findとは
11.フィボナッチ数列の計算量について 2 Union-Findの仕組み
11.3 Union-Findの計算量を削減する工夫
11.4 Union-Findの工夫その1:union by size
11.5 Union-Findの工夫その2:経路圧縮
11.6 Union-Findの実装
11.7 Union-Findの応用:グラフの連結成分の個数
11.8 まとめ

12章 ソート
12.1 フィボナッチ数列の計算量について フィボナッチ数列の計算量について ソートとは
12.2 ソートアルゴリズムの良し悪し
12.3 ソート(1):挿入ソート
12.4 ソート(2):マージソート
12.5 ソート(3):クイックソート
12.6 ソート(4):ヒープソート
12.7 ソートの計算量の下界
12.8 ソート(5):バケットソート
12.9 まとめ

13章 グラフ(1):グラフ探索
13.1 グラフ探索を学ぶ意義
13.2 深さ優先探索と幅優先探索
13.3 再帰関数を用いる深さ優先探索
13.4 フィボナッチ数列の計算量について フィボナッチ数列の計算量について 「行きがけ順」と「帰りがけ順」
13.5 最短路アルゴリズムとしての幅優先探索
13.6 深さ優先探索と幅優先探索の計算量
13.7 グラフ探索例(1):s-tパスを求める
13.8 グラフ探索例(2):二部グラフ判定
13.9 グラフ探索例(3):トポロジカルソート
13.10 グラフ探索例(4):木上の動的計画法
13.11 まとめ

14章 グラフ(2):最短路問題
14.1 フィボナッチ数列の計算量について 最短路問題とは
14.2 最短路問題の整理
14.3 緩和
14.4 DAG上の最短路問題:動的計画法
14.5 単一始点最短路問題:ベルマン・フォード法
14.フィボナッチ数列の計算量について フィボナッチ数列の計算量について 6 単一始点最短路問題:ダイクストラ法
14.7 全点対間最短路問題:フロイド・ワーシャル法
14.8 参考:ポテンシャルと差分制約系
14.9 まとめ

15章 グラフ(フィボナッチ数列の計算量について 3):最小全域木問題
15.1 最小全域木問題とは
15.2 クラスカル法
15.3 クラスカル法の実装
15.4 全域木の構造
15.5 クラスカル法の正当性
15.6 まとめ

16章 グラフ(4):ネットワークフロー
16.1 ネットワークフローを学ぶ意義
16.2 グラフの連結度
16.3 最大流問題と最小カット問題
16.4 フォード・ファルカーソン法の実装
16.5 応用例(1):二部マッチング
16.6 応用例(2):点連結度
16.7 応用例(3):プロジェクト選択問題
16.8 まとめ

17章 PとNP
17.1 問題の難しさの測り方
17.2 PとNP
17.3 P ≠ NP予想
17.4 NP完全
17.5 多項式時間帰着の例
17.6 NP困難
17.7 停止性問題
17.8 まとめ

18章 難問対策
18.1 NP困難問題との対峙
18.2 特殊ケースで解ける場合
18.3 フィボナッチ数列の計算量について 貪欲法
18.4 局所探索と焼きなまし法
18.5 分枝限定法
18.6 整数計画問題への定式化
18.7 近似アルゴリズム
18.8 まとめ

関連記事

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次
閉じる