1

これは先週のクイズでした。以下の質問の答えはLine：3だと思いました。しかし、インストラクターは、4行目が優れていると私に言いました。まだ理由がわからないのですか？そして別の質問につながります、どうすれば私の最良の増分を知ることができますか？

ここに画像の説明を入力してください

私が聞きたい2番目の質問は、Summationsを使用して以下の実行中のコードのコストをどのように表すかです。私はたくさん検索しましたが、私が見つけたのは、これに関係のないコードの複雑さを見つけることだけでした。

皆さんが私にすべてをクリアしてくれることを願っています。

4

1 に答える 1

0

整数に2を掛けると、コンパイラは自動的にそれを右シフト演算に変換します（これは非常に効率的です）。また、整数を比較するよりも浮動小数点数を比較する方がコストがかかります。4行目が実行される回数は3行目が実行される回数と同じであるため、4行目が総コストを最もよく表します。

コードの総コスト

= total cost of comparing i with n and incrementing i + 
  total cost of comparing j with n and right shifting j + 
  total cost of comparing two floats + 
  total cost of incrementing a float

<= c1*n + c2*n*n/2 + c3*n*n/2 + c4\sum_{1 <= i <= n, 1 <= k <= n/2}d(i,2k), 
                 where d(i, j) is 1 if array[i] > array[j] and 0 otherwise.

<= c1*n + c2*n^2  + c3n^2 + c4n^2

<= c*n^2 for some constant c
于 2012-09-28T13:50:00.470 に答える