big-o - 大写符号工作

big-o - 大写符号工作,第1张

我使用Big-O符号时间复杂度很高 我有三个例子 我试图弄清楚Big(o)

  • 第一个例子是

     sum = 0;
     for(i=0; i<m/3; i  ){
     System.out.println(“*”);
     for(j=0; j<n; j  )
     for(k=0; k<10; k=k 2)
     sum  ;
     }
    

    我认为这个是O(mn),第一个循环工作m / 3次,第二个循环工作n次,第三个循环工作10次 然后O(mn)

  • 第二个例子是

    sum = 100;
    for(i=0; i<n; i  ){
    sum  ; 
    }
    for(j=10; j<n; j  )
    for(k=1; k<m; k*=2)
     sum  ;
    

    Big-O = O(log(m)),其中执行的操作数为n ((n - 10)* log(m))

  • 第三个例子是

      sum = 0;
      for(i=2; i<n; i  ){
      for(j=3; j<n; j =2){
             sum  ;
      }}
     for(k=1; k<m; k*=2)
     sum  ;
    

    这里我认为Big-O = log(m)n ^ 2 ???

    是正确的吗?

    最佳答案:

    1 个答案:

    答案 0 :(得分:3)

    这是:

    1. O(m / 3 * n * 5)= O(mn * C)= O(mn)
    2. O(n (n - 10)* log(m))= O(n * log(m))
    3. O((n-2)*(n-3)/ 2 log(m))= O(n 2 log(m))= O(n 2功能
    4. 下次请格式化由括号更清晰定义的代码块 在3. O(n 2 log(m))→O(n 2 )中,因为f(x)= x 2 &gt;当x→ ∞时,g(x)= log(x)。

      <强> UPD 即可。你的代码(格式化得更好):

      sum = 0;
      // let's go from inner most loop: (n - 3)/2 actions or simpler n/2 or just n
      for(i=2; i<n; i  ) {
          for(j=3; j<n; j =2) {
              sum  ;
          }
      }
      

      因为在大O常数中无关紧要,即O(5)= O(1)或O(18 * x 5 )= O(x 5 )。
      例如,这就是为什么big-O中的log没有基数:O(log 2 x)= O(log(x)/ log(2))= O(log (x)* Const)= O(log(x)),其中log - 是自然对数(基数为e

      我们再来一次:

      sum = 0;    
      // n actions in inner loop n times. So it's O(n^2)
      for(i=2; i<n; i  ) {
          for(j=3; j<n; j =2) {
              sum  ;
          }
      }
      // THEN there're another log(m) actions
      for(k=1; k<m; k*=2) {
          sum  ;
      }
      

      所以我们总结一下:O(n 2 log(m))。

      现在让take a look函数x 2 和log(x)。如您所见,x 2 的增长速度远远快于log(x)。当x→ ∞时,可以通过研究l(x)= log(x)/ x 2 的极限来实现证明。它等于零 这就是为什么在和x 2 log(x)中,第一个术语占主导地位。所以[x 2 log(x)] / x 2 = 1 o-small(x),即它们在复杂性方面是相等的。这就是为什么O(n 2 log(m))= O(n 2 )。

      原始方程有两个不同的变量依赖。如果它们都是独立的,最好“计算”它们两者:O(n 2 log(m))。

      本文经用户投稿或网站收集转载,如有侵权请联系本站。
  • 发表评论

    0条回复