时间的效果和效率

Question

我编写了两个程序，以找到一个数字的分隔线数。

第一个功能的代码少于第二个功能，但对于500 000之类的数字，它可以进行250 001迭代。

但是，具有更多代码的第二个函数可以进行800个迭代。

关于时间复杂性，哪个功能比其他功能更有效？

int divisors(int n) 
{
  int i, count = 1;
  
  for (i = 1; i <= n / 2; i++) 
  {
    if (n % i == 0)
      count ++;
  } 
  
  return count;
}


 int divisors(int nbr)
 {
    int div_1=1;
    int div_2=0;
    int n_div=0;
    
    
    do {
        
        if (nbr % div_1 == 0)
        {
            div_2 = nbr / div_1;
            if(div_1==div_2)
            {
                n_div+=1;
            }
            else
            { n_div+= 2; }
        }
        div_1 ++;

    }while(div_1<div_2);

    return n_div;
}

Answer 1

第一个是 o（n） 用for（i = 1; i = 1; i＆lt; i＆lt; ; = n / 2; i ++）< / code>。

第二个是O（sqrt（n）），其div_2 = nbr/div_1; and } while（div_1＆lt; div_2）; - 较低的时间复杂性。

有足够大的n，第二个是更效率的时间。

---

注意：两个循环都使用a％b - 一个昂贵的操作。第二种使用a / b < / code> - 另一个昂贵的操作。良好的编译将看到附近的这两个操作，并以大约一个成本进行执行。

---

也许是第三个变更？ （也是O（sqrt（n）））
这使用div（）来计算商的弱编译器，并在一个操作中剩余，这些编译器不会将常见的/，％一起折叠。它将div_1 == div_2移至循环外部，因为它永远不会超过一次。

#include <stdlib.h>

// Untested illustrative code.
int divisors3(int nbr) {
  int count = 0;
  int divisor = 1;
  div_t qr = { .quot = n };
  // Add 2 to the count for the distinct divisor and quotient.
  while (divisor < qr.quot) {
    if (qr.rem == 0) {
      count += 2;
    }
    divisor++;
    qr = div(nbr, divisor);
  }
  // Add 1 to the count for the common divisor and quotient.
  if (divisor == qr.quot) {
    if (qr.rem == 0) {
      count++;
    }
  }
  return count; 
}

---

更屈服的代码可以利用Divisor是nbr的多因素。