質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

受付中

計算量のlogCの出どころを知りたい。

SmaSTATION
SmaSTATION

総合スコア16

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

2回答

0グッド

1クリップ

331閲覧

投稿2022/11/20 05:22

前提

下記に示すプログラムの計算量を知りたいです。
解答では、(NlogNlogC)となっています。
NlogNまでは、二分探索とソートの処理というめぼしはつくのですが、logCの行方がわからず困っております。

該当のソースコード

C++

1#include <iostream> 2#include <vector> 3#include <algorithm> 4using namespace std; 5 6int main() { 7 long long N, K; 8 cin >> N >> K; 9 vector<long long> a(N), b(N); 10 for (int i = 0; i < N; ++i) cin >> a[i]; 11 for (int i = 0; i < N; ++i) cin >> b[i]; 12 13 // b はあらかじめソートしておく 14 sort(b.begin(), b.end()); 15 16 // 判定問題 17 auto check = [&](long long x) -> bool { 18 long long cnt = 0; 19 for (int i = 0; i < N; ++i) { 20 cnt += upper_bound(b.begin(), b.end(), x / a[i]) - b.begin(); 21 } 22 return (cnt >= K); 23 }; 24 25 // 二分探索 (right は十分大きな値に設定) 26 long long left = 0, right = 1LL<<60; 27 while (right - left > 1) { 28 long long mid = (left + right) / 2; 29 if (check(mid)) right = mid; 30 else left = mid; 31 } 32 cout << right << endl; 33}

試したこと

再度ひとつずつ、計算量を見てみるも、N、logNしか見当たらずでした。

補足情報(FW/ツールのバージョンなど)

解説には最大値とありますが、そもそもプログラム内にmax関数なんて使っていないような気がしています...
参考にした解説ページ
リンクに飛べます。

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答2

1

checkにNlogNかかるのはループ構造から自明とおもいます。
問題は外側のwhileが何回回るかで、このプログラム例ではrightの初期値は1<<60なので60回なわけですが、これがlogCに相当します。
というのもrightはmax(a)×max(b)が上限だからです。実際の値から求めてもいいですが、a,bの最大は1e9である前提なので2^30(1.07e9)で近似して2^60が出てくるわけです。

投稿2022/11/20 12:24

matukeso

総合スコア1425

actorbug👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

0

あまく詳しくないので,間違っているかもしれませんが,
logCは比較処理,具体的にプログラムの中では「if check(mid)...」の回数に関係するものだと思います。
値の比較処理自体,乗除加算と同様に演算時間がかかります。

投稿2022/11/20 05:57

ujimushi_sradjp

総合スコア1503

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。