ここから本文です

c++ lis 下2つのコードで計算速度があまり変わらないのはなぜでしょうか。

hat********さん

2019/2/2800:00:03

c++ lis
下2つのコードで計算速度があまり変わらないのはなぜでしょうか。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3391701
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3391875#2

閲覧数:
52
回答数:
1

違反報告

ベストアンサーに選ばれた回答

fkh********さん

2019/3/101:28:03

なぜこのコードでこの問題が解けるのかちょっと理解できないのですが、コードの動き方の話だけをすると、このコードではそこの計算量が支配的ではないからです。

問題の箇所だけ見ると、stlを使っているほうが2分探索になっておりちゃんと速くなっているのですが、処理がここに来る回数がかなり少ないです。

たとえばn=100000で5回程度しか通らなかったりしていますので、ここを速くしても全体の計算時間は変わりません。

質問した人からのコメント

2019/3/2 10:20:47

入力例1
5
5 1 3 2 4
5
1
1 3
1 2
1 2 4
のように最後しか操作しないですね。
ありがとうございます。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる