プログラミング学習記録【13日目】

街のマーベルファンはにわか

一度も触れていない僕の一番好きなもの。

アイアンマンに小さい頃から憧れている。
映画アイアンマンからこの世界に踏み込んだが、今に至るまでに幾度見直したか覚えていないほど見た。
マーベル作品のアベンジャーズのヒーローはみんな好きなのだが、アイアンマンは郡を抜いていて、映画だけにとどまらず、漫画にも手を出して背景を確認するほどなのだ。
そして好きはそこだけにとどまらず、マーベル映画は毎作チェックし、ドラマAgent of SHIELDやエージェント・カーターなどもチェックして舞台の裏側も確認している。

ここで少しチェックしてほしいのだが、今に至るまでにマーベル映画は23本、ドラマに至っては100本以上あり、Netflix限定のヒーローもいるのだ。
僕は個人的に、ここまでマーベルヒーローをチェックしてる人はそんなにたくさんはいないと思っている。なにせ時間がかかりすぎるのだ。
僕は、大学の勉強をしながらバイトをし、独学したい分野もある中でこの作品を追う、と決めたときに、他の趣味に時間を割くことを諦めたほどだ。

例えばエンドゲームでスティーブ･ロジャースがカーターに会いに行ったシーン。
確かにキャプテン・アメリカのファーストアベンジャーでカーターとは会っているし、シビル・ウォーでカーターの最後に立ち会うなどしているから、エンドゲームのスティーブのあの行動は、映画を追っている人なら理解はできるだろう。
ただ、そこにどんな思いがあるのか、カーター側の思いはどんな物があるのか、といった背景は、ドラマを確認した人にしかわからないし、そこに至るスティーブの決断といったものは、原作を知っている人にしか理解できない部分があると思う。

もちろん僕がマーベルガチ勢なのは、仲のいい人には隠したことがないのだが、スパイダーマンがMCU(Marvel･Cinematic･Universe)に参入したときやインフィニティー･ウォー、エンドゲームのときなどは、どの順番で見れば良いのか、とか、最短で追いつきたいなど質問され、辟易したものだ。みんなには公開順に全部見ろ、で突き返している。
僕の周りでもそうなのだから、街中にあふれているMarvelのロゴ入りの服やバッグなどを身に着けている中高生や若者たちは本当にファンなのか?と疑問に思ってしまう。
大方、アベンジャーズと名のついた映画だけを追ってエンドゲームを見たりしたのではないだろうか…。

最近流行りだから聞いてる程度のアーティストのバンドTとかグッズって、街中に来て行ったりつけていったりしないと思う。
何が言いたいのかと言うと、もっとMarvelのことを深く知ってほしい。そのうえでグッズを身につけてほしい。
にわかはお断り、という精神はないのだが、よく知りもしないものを背負ってほしくない、とは思ってしまうのだ。
僕はこの程度の小さい心の持ち主なのである。

2.06.計算量

プログラムを作成する際の計算手順のことをアルゴリズムと呼ぶ。
アルゴリズムの性能を比較する方法の一つに、計算量、という指標がある。
｢プログラムの実行に必要な計算のステップ数が入力に対してどのように変化するのか｣という指標を時間計算量、｢プログラムの実行に必要なメモリの量が入力に対してどのような変化をするのか｣という指標を空間計算量という。
厳密な計算ステップ数や必要な記憶領域の量は環境により変わってしまうので、時間計算量や空間計算量の表現としてオーダー記法が用いられることがある。係数を省略して項をNをとし、定数を1として、Nを大きくしたときに一番影響が大きい項を取り出し、O()の括弧内に書く。
入力の上限を見積もってプログラムを作る必要があり、O(N)の時間計算量ならNが10の8乗ほどの計算をするのに1秒ほどかかるのでこれを目安にすると良い。

EX21.計算量の見積もり

次のプログラムのそれぞれの関数の計算量を見積もって、最も経産次官のかかる関数を呼び出している行をコメントアウトせよ。
制限時間は2秒、10の8乗回程度の計算が可能。

#include <bits/stdc++.h>
using namespace std;

int f0(int N) {
 return 1;
}
 
int f1(int N, int M) {
 int s = 0;
 for (int i = 0; i < N; i++) {
   s++;
 }
 for (int i = 0; i < M; i++) {
   s++;
 }
 return s;
}

int f2(int N) {
 int s = 0;
 for (int i = 0; i < N; i++) {
     int t = N;
     int cnt = 0;
     while (t > 0) {
       cnt++;
       t /= 2;
     }
     s += cnt;
 }
 return s;
}


int f3(int N) {
 int s = 0;
 for (int i = 0; i < 3; i++) {
   for (int j = 0; j < 3; j++) {
     s++;
   }
 }
 return s;
}

int f4(int N) {
 int s = 0;
 for (int i = 0; i < N; i++) {
   for (int j = 0; j < N; j++) {
     s += i + j;
   }
 }
 return s;
}

int f5(int N, int M) {
 int s = 0;
 for (int i = 0; i < N; i++) {
   for (int j = 0; j < M; j++) {
     s += i + j;
   }
 }
 return s;
}

int main() {
 int N, M;
 cin >> N >> M;

 int a0 = -1, a1 = -1, a2 = -1, a3 = -1, a4 = -1, a5 = -1;

 // 計算量が最も大きいもの1つだけコメントアウトする
 a0 = f0(N);
 a1 = f1(N, M);
 a2 = f2(N);
 a3 = f3(N);
 //a4 = f4(N);
 a5 = f5(N, M);

 cout << "f0: " << a0 << endl;
 cout << "f1: " << a1 << endl;
 cout << "f2: " << a2 << endl;
 cout << "f3: " << a3 << endl;
 cout << "f4: " << a4 << endl;
 cout << "f5: " << a5 << endl;
}

これに関しては計算量が多いのを見れば良いので1つずつ確認していくと
f0はO(1)、f1はO(N+M)、 f2はO(NlogN)、 f3はO(1)、 f4はO(Nの2乗)、 f5はO(NM)だとわかるので、今回計算量が最も多いのはf4。よってこれをコメントアウトする。