「再帰関数の計算量を見積もれ」という問題に自信がない件。

「Pythonによるプログラミング入門」の練習問題7.6の計算量を見積もれっていう問題の答えって、「5のn乗に比例する」で合ってますかね？（雑な質問の仕方）

この記事に事の顛末を記録しています（ややチラ裏）。

「再帰関数の計算量を見積もれ」が難しい。

「Pythonによるプログラミング入門」を読み進めているのですが、練習問題に所々で出題される「このプログラムの計算量を見積もれ。」が分かりません。

なにしろ、今まで気にしていませんでしたから。

Pythonによるプログラミング入門　東京大学教養学部テキスト: アルゴリズムと情報科学の基礎を学ぶ

もちろん、自分なりの答えはありますが、それが正解かどうか分からない状態です。下記Qiitaを読み、確認しながらすすめているので、だいたいは、正解だと思うのですが…

[初心者向け] プログラムの計算量を求める方法 - 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の範囲では「指数関数的に増える」というのは間違い無いようです。