質問: 1 S= [[0, 1, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 0]] print(square(S, i, j)) #2 ```
回答: 計算量に関する考え方が根本的に間違っています。 問題に対して変化する数量、この問題の場合はiやjに対して計算量がどれぐらいのオーダーで変化するかどうかです。たとえば、もし、1x1行列でも3x4行列でも10000x10000行列でも計算回数(時間計算量)もメモリ使用量(空間計算量)も変わらないようなアルゴリズムであればO(1)です。しかし、もし、1x1行列の計算量にたいして、3x4行列では最大で4倍、10000x10000行列では最大で10000倍、ほとんどの場合で最大でmax(i, j)倍になるようであれば、O(max(i,j))であろうとなります。つまり、3x4行列だけを考えてもダメで、色々変化していくときにどうなるかを考える必要があります。 このように、変化して行くであろう数量に対して、計算回数やメモリ使用量がどれくらいのオーダー(n倍なのか、n^2倍なのか、n!倍なのか、それとも変わらないのか)で必要になっていくのかを見ていきます。NPPさんが、10000x10000行列も3x4行列も1x1行列も最悪の場合の計算回数が変わらないと思うのであれば、それはきっと時間計算量は定数時間O(1)なのでしょう。はたして、本当にそう思いますか?もし、そうではないと思うのなら、どの値にどのように依存しているのかを考え直してください。