English 字幕

← 18-24 Expected Running Time

埋め込みコードを取得する
1言語

字幕を編集する
ダウンロードする

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. And the exact analysis of this algorithm here reveals that if the Boolean formula
  2. has a satisfying assignment, then this assignment is found where the probability of about
  3. 3/4^n times some polynomial of n and I'll just write that as p(n) here.
  4. So how many times do you have to run this algorithm given the success probability here
  5. to find the satisfying assignment on average, assuming there exist one.
  6. Now, if you have had a basic statistics course, you should already know
  7. that the expected running time, so how often we have to run this algorithm until we find
  8. a satisfying assignment assuming the Boolean formula has one is the time
  9. for a single run divided by the success probability of one run.
  10. And of course, I'm going to let you figure our the final answer for this as our next quiz.
  11. So is the expected running time O(3/4^n times the polynomial of n) which is this polynomial here
  12. times some other polynomial, which will represent the time for one run of this algorithm here
  13. or is it O(4/3^n times the polynomial of n) times the time required for this algorithm here,
  14. or is it O(3/4^n times the polynomial for this algorithm here) divided by this polynomial here,
  15. or finally, is it O(4/3^n times the time required to run this algorithm here) divided by this polynomial.