SICP - day4

本投稿の目的

Structure and Interpretation of Computer Programsを読み始めて二日目。
毎日ログをつけなければサボると思い、日記程度にまとめます。DS勉強してました。Pythonしか書けないです。（書けるといっても、Vibe Coding勢。）（著者はあまりどっぷり何かに浸かったことがない人間。）

〜P47の半分まで終わった。
金土で更新する暇がなかったので、1日とカウントさせてください。（進捗はございます）

気づいたこと

• 両替問題面白いけど、理解するのに結構時間かかってしまった。学びです。
• オーダーがわからなすぎる
  不明点は以下
  • ステップ数と必要な空間の指していること
    ステップ数は、何ステップ行ったかと想定している。
  • k_1*f(n) <= R(n) <= k_2*f(n)となるR(n)の増加オーダーがTheta(n)て定義されるって、まずそもそもfって何？という話だし、イメージでも全く想像がつかない。
    →チャッピに聞いたところ、オーダーとは入力を大きくしたとき、どれくらい大変になるかということでした。
    →ステップ数はコンピュータが何回くらい仕事をするか・空間は同時にどれくらい覚えておかなきゃいけないかとのことでした。
    →それってすなわち、Theta(2^n)よりも、Theta(log(n))の方が優秀？なぜならインプットがn倍になっても、ステップ数・空間が小さい方があまりリソースを使わなくて良いから？
    例）入力をn倍したところ、計算回数もn倍ならTheta(n)
    →練習問題1.16も解いていないので、どなたか親切な方、理解が合っているか否かご教授をお願いします🙇

練習問題1.9

これは(& 気合い (理解 (+ 再帰 反復 の))があればいけます。ノートに処理を転記しましょう

練習問題1.10

これもノートに処理転記＆高校数学のノリで解けます。気合いです。
分かったこととして、

• 木の再帰プロセスで必要なステップ数は、木のノード数に比例する
• 必要な空間は木の最大深度である

と言うことが挙げられます

練習問題1.11

これは気合いで三元一次方程式で解こうと思いましたが、結局とけず。。。
チャッピにヒントだけ教えていただいたので、解きました。
ヒントは、変数定義＆各for文内でのそれら変数の遷移です

練習問題1.12

これは漸化式を記載できればできます！！
→漸化式を描こうという姿勢が大事だと気づく

練習問題1.13

これはむずい！！非常に！
ヒントはチャッピにもらいつつ解いたのですが、フィボナッチ数列とphiとpsiの漸化式がかければ、比較可能であり、尚且つそれらが同じであるということを証明すればできます。

練習問題1.14

この増加オーダー全くわからずじまいでした。。
どなたかわかりやすいイメージを教えてください。見ていただけたら！
分からない点は

• ステップ数と必要な空間の指していること
  ステップ数は、何ステップ行ったかと想定している。
• k_1*f(n) <= R(n) <= k_2*f(n)となるR(n)の増加オーダーがTheta(n)て定義されるって、まずそもそもfって何？という話だし、イメージでも全く想像がつかない。

練習問題1.15

これは、sine関数がストップする条件式を導ければOKです。
また、なんとなーくですけど、ステップ数と空間のオーダーは同じ関数がなん度も呼び出されるだけなので、同じかなというイメージを持ちつつでした！