开发者

Algorithms Run time Complexity

Hi I suppose to write a program that show the run time complixity I solved two but can't solve the third the code is :

{
class Program
{
    /* static long F1(long n)
     {
         long sum = 0;
         for (int k = 1; k <= n; k++)
 开发者_JS百科        {
             for (int j = 1; j <=n*n; j++)
             {
                 for (int m = 1; m <=j; m++)
                 {
                     sum = sum + 1;
                 }
             }
         }
         return sum;
      }
    static long F2(long n)
     {
         long sum = 0;
         for (int k = 1; k <= n; k++)
         {
             for (int j = 1; j <= n ; j++)
             {
                 for (int m = 1; m <= j; m++)
                 {
                     sum = sum + 1;
                 }
             }
         }
         return sum;

     }*/
  static long F3(long n)
  {
      long prod = 1;
      long m;
      long i = 2;
      long s = n;
      while (n >= 1)
      {
          m = 1;
          while (m <= n)
          {
              prod = prod * 2;
              m = m + 1;
          }
          n = s / i;
          i++;
      }
         return prod;

     }


    static void Main(string[] args)
    {
       // Console.WriteLine(F1(100));
       // Console.WriteLine(F2(2200));
     Console.WriteLine(F3(10000));
        long x; 
        DateTime d1=DateTime.Now;
        x=d1.Ticks;
     // F1(600);  
    //    F2(2200);
        F3(1000);
        DateTime d2=DateTime.Now;
        x=(d2.Ticks-x)/10000000;
        Console.WriteLine("x=" + x.ToString());
        Console.ReadLine();
    }
}

}

now the correct answers that F3 should show are

300000000   0   5
400000000   0   4
500000000   0   7

but all what i got is o o o

while the F2 and F1 are showing right answers can any one help


What I wonder is: isn't it just a matter of integer division?

I mean here: x=(d2.Ticks-x)/10000000;

Note: I'm not practical with C#, it's just an hypothesis


 x=(d2.Ticks-x)/10000000

is where the problem lies. F3 runs for less than a second and you are doing integer divisions: remember that 900/1000 == 0.

A simple (rather unelegant) fix is to do a floating point division:

 x=(d2.Ticks-x)/10000000.0

You might want to use TimeSpans intead, which are made to measure elapsed time:

DateTime start = DateTime.Now;

// Do stuff

DateTime end = DateTime.Now;
TimeSpan elapsed = end - start;
double secondsElapsed = elapsed.TotalSeconds;
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜