「再帰関数の計算量を見積もれ」という問題に自信がない件。
「Pythonによるプログラミング入門」の練習問題7.6の計算量を見積もれっていう問題の答えって、「5のn乗に比例する」で合ってますかね？（雑な質問の仕方）
この記事に事の顛末を記録しています（ややチラ裏）。
「再帰関数の計算量を見積もれ」が難しい。
「Pythonによるプログラミング入門」を読み進めているのですが、練習問題に所々で出題される「このプログラムの計算量を見積もれ。」が分かりません。
なにしろ、今まで気にしていませんでしたから。
もちろん、自分なりの答えはありますが、それが正解かどうか分からない状態です。下記Qiitaを読み、確認しながらすすめているので、だいたいは、正解だと思うのですが…
しかし、このQiitaの記事でも、再帰関数の計算量の見積もりについては、省略されています。
どうしても自信が無い練習問題7.6
「Pythonによるプログラミング入門」の練習問題を進めていて、どうしても自信が無いのがVicsekフラクタルを作る再帰関数の計算量を見積もる練習問題7.6（page 133-134）です。コードは下記の通りです。
なお、itaライブラリは、この本特有のものです。このコードでは2次元配列を作るのに使っているだけです。
import ita
def ex7_6(n):
image = ita.array.make2d(3 ** n, 3 ** n)
vicsek_main(image, 0, 0, 3 ** n)
return image
def vicsek_main(image, x, y, size):
if size == 1:
# if-part
image[x][y] = 1
else:
# else-part
m = size // 3
vicsek_main(image, x + m , y , m)
vicsek_main(image, x , y + m , m)
vicsek_main(image, x + m , y + m , m)
vicsek_main(image, x + 2 * m, y + m , m)
vicsek_main(image, x + m , y + 2 * m, m)「この再帰関数の時間的な計算量見積もりをせよ」という問題です。
たぶん、ガチ勢には笑われるレベルの問題なんだと思いますが、考えた事を書き連ねます。
再帰関数の計算量について、考えた事
まず、n=1, 2, 3でそれぞれ、vicsek_main関数が何回呼び出されるのかを考えました。
n=1の時：if-partを通る呼出が5回、else-partを通る呼出が1回（=1）
n=2の時：if-partを通る呼出が25回、else-partを通る呼出が6回（=1+5）
n=3の時：if-partを通る呼出が125回、else-partを通る呼出が31回（=1+5+25）
なので、vicsek_main関数が呼び出されるのは、下式のようになると考えました。
O記法で書けば、O(5^n)なので、「計算量は5^nに比例する」が答えだと思いますが、自信はあまりありません。合ってますかね？
一応、計算時間をグラフにしましたが、n=0～9の範囲では「指数関数的に増える」というのは間違い無いようです。
