大写符号工作

问题描述 投票:1回答:1

我是时间复杂的新使用Big-O表示法我有三个例子,我试图找出大(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 ??? 这是对的吗???
  • big-o
    1个回答
    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(n2 + log(m))= O(n2)

    请下一次格式化由括号更清晰定义的代码块。 在3. O(n2 + log(m))→O(n2)中,因为f(x)= x2> g(x)= log(x),当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 * x5)= O(x5)。 例如,这就是为什么big-O中的log没有基数:O(log2x)= 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(n2 + log(m))。

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

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

    © www.soinside.com 2019 - 2024. All rights reserved.