算法

时间复杂度

1. 【大O符号表示法】，公式：T(n) = O(f(n))

   for(i=1; i<=n; ++i)
   {
      j = i;
      j++;
   }
   

   这段代码的时间复杂度为：O(n)，公式中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度

空间复杂度

1. 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义

2. 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

   int i = 1;
   int j = 2;
   ++i;
   j++;
   int m = i + j;
   

3. 这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

   int[] m = new int[n]
   for(i=1; i<=n; ++i)
   {
      j = i;
      j++;
   }
   

评论