質問: tmp return result ``` パフォーマンス結果 `Detected time complexity:O(N ** 2)`
回答: 「FrogRiverOne」という問題の内容が理解できていないのだと思います。 ちゃんと理解できていれば、もっと素直なコードが書けたでしょうから。 「日本語で書かれた記事」から推測すると 『川岸に蛙が居ます。 川には、岸にある樹から葉っぱが落ちてきます。 川の流れはとても穏やかなので、落ちた葉っぱはほとんど動きません。 こちらの岸から向こう岸まで、葉っぱが連なって落ちたら、蛙は葉っぱを伝って向こう岸まで渡ることができます。 川の幅は、葉っぱX枚分です。 葉っぱは1秒に1枚落ちてきますが、その落ちる場所はいろいろです。 配列Aは葉っぱの落ちる場所を示していて、開始からt秒後に落ちる葉っぱの位置(岸から何枚分離れているか)はAのt番目にあります。 蛙が渡れるようになるのは、開始から何秒後かを答えなさい』 という感じでしょう。 「日本語で書かれた記事」にコードが示されていますが、その構成は以下のようになっています あ:準備)葉っぱがある(そこの落ちた事がある)かどうかを記録する配列B(大きさは、川幅分の葉っぱの枚数)を用意して、時間(t)は0にする。 い:毎秒行う処理)配列Aの内容(葉っぱの落ちる位置)を順に見ていって、その位置に葉っぱが落ちた事が無ければ(配列Bのその位置の値が0なら)、配列Bのその位置の値を1にして(葉っぱがあることを記録)、向こう岸までの使える葉っぱの数(cnt)を+1する。(葉っぱの落ちる場所が向こう岸の先(Xより大きい)なら無視(なにもしない)) 時間(t)を+1する。 う:完了の判断)使える葉っぱの数がXに等しくなったら、向こう岸まで葉っぱが連なって渡れるようになった訳だから、その時のtを答えて、終わり。 使える葉っぱの数がXと等しくないなら、足りない葉っぱがあるので、"い"に戻る。 このプログラムでは、"い"の部分が何度か繰り返し実行されますが、繰り返しのループは1つだけなので、高々1次(配列Aの長さ程度)の繰り返しにしかなりません。 質問に書かれたコードは、配列Aの繰り返しループ(外側のループ)の中に、別のループ(何を意図したものか判りませんでした)があるので、2次("配列Aの長さ" * X)の繰り返しとなります。("Detected time complexity:O(N ** 2)" 時間複雑度がNの二乗というのは、そういう意味です) この問題はO(N)の複雑性しかありません。それに対してO(N**2)のコードを回答をしたら「パフォーマンスが悪い」と評価とされますよね。 パフォーマンスを上げるには、”無駄なことをしない”ことを徹底する。 それしかありません。 この操作は必要なのか? を問い続けると、パフォーマンスの良いコードが書けるようになると思います。