数据结构中的时间复杂度与空间复杂度

举个简单的例子，要从0加到n，我们会这么写：
int sum = 0;
for(int i = 0; i<=n; ++i)
{
  sum += i;
}
一共算了n次加法，那么就说这个时间复杂度是O(n)。当然O(n)的精确的概念是，是n的最高次方，比如，某个计算共计算了3n + 2次，那么这个时间复杂度也是O(n)，因为3n + 2中的最高次方是n。

如果代码这么写：
int sum = 0;
for(int i = 0; i<=n; ++i)
{
  for(int j = 0; j <=n; ++j)
  {
  sum += (i + j);
  }
}

很显然一共算了n^2次加法，那么就说这个时间复杂度是O(n^2)，和上面类似，如果某个算法计算了3*n^2 + n + 1次，其时间复杂度仍然是O(n^2)，因为3*n^2 + n + 1中最高的次方是n^2

所谓O(1)就是计算的次数是个常量，我们还以上面从0加到n的例子来说，如果我们用等差数列的公式，那么，代码可以这么写：
int sum = n * (n + 1) / 2
不管n有多大(当然不能溢出了)，通过上面的公式只需计算一次，也就说计算的次数是不变的，这种情况的时间复杂度就可以说成O(1)。 再比如如果某个计算，不管其他条件怎么变化，均只需计算5次即可得出结果，那么这种情况的时间复杂度，也是O(1)。

 

如果存在正常数c和n0使得当N>=n0时T(N)<=cf(N),则记为T(N)=O(f(N))

这个意思是说最后总会存在某个点n0，从他以后c*f(N)总是至少与T(N)一样大

 

 我们需要掌握的重要结论为：

法则1：

如果T1(N)=O(f(N)) 且 T2(N)=O(g(N))，那么

a)  T1(N) + T2(N) = max(O(f(N)),O(g(N)))

b)  T1(N)*T2(N)=O(f(N)*g(N))