时间复杂度

void sum(int n){
 int count = 0;       //一次
 for(int i = 0;i<n;i++){ //n + 1 次
   count += i; //n 次
 }
 System.out.println(count); //一次
}

上面算法f(n) = 2n + 3;

 void sum(int n){
  int sum = 0;
  sum = (1+n)*n/2;
 }
 System.out.println(sum);

上面算法f(n) = 3；

在进行算法分析时，算法执行总次数T(n)是关于问题规模n的函数。进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。 它表示随问题规模n的增大，算法时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。

这样用大写O()来体现算法的时间复杂度的记法，我们称大O记法。一般情况下，随问题规模n的增大T(n)的增长率最慢的算法为最优算法。

通常O(1)叫常熟阶，O(n)叫线性阶，O($$n^2$$)叫平方阶。

推导大O阶：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

得到的结果就是大O阶。

1. 常数阶
   执行时间恒定（无论n是多少）的算法，都称为常数阶。记作O(1)。

2. 线性阶
   线性阶的循环结构会辅助很多。要确定某个算法的阶次，我们常需要确定某个语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键是要分析循环结构的运行情况。

   int i；
   for(i = 0; i< n;i++){
   /*时间复杂度为O(1)的程序步骤序列*/
   }
   

   上面这段代码，它的时间复杂度为O(n)。因为循环体中的代码要执行n次。

3. 对数阶

   int count = 1;
   while (count < n){
   count = count *2;
   /*时间复杂度为O(1)的程序步骤序列*/
   }
   

   上面算法中，count 2 在运行x次之后 count 2 = n, $$2^x = n$$,$$x = \log_2 n$$。所以这个循环的复杂度为O($$\log_2 n$$)

4. 平方阶

 int i,j;
 for(i = 0;i < n;i++){
  for(j = 0;j < n;j++){
   /*时间复杂度为O(1)的程序步骤序列*/
  }
 }

上面例子是一个循环嵌套，上面我们知道内循环的时间复杂度为O(n)，而外循环不过是O(n)再次执行n次，所以上例子的时间辅助度为O($$n^2$$)。

那么下面这个循环的时间复杂度怎么求？

int i,j;
for(i = 0;i < n;i++){
 for(j = i;j < n;j++){
  /* 时间复杂度为O(1)的程序步骤序列 */
 }
}

当i = 0 时，内循环执行n次，当i = 1 时，内循环执行n-1 次，当i = n-1 时，内循环执行1次，所以总执行次数为：

$$ n+(n-1)+ \cdots +1 = \frac{n*(n+1)}{2}$$
大O记法记作O($$n^2$$)。

常见时间复杂度

常用的时间复杂度所耗费的时间从小到大依次是：

$$O(1) < O(\log_n) < O(n) <O(n\log_n) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n) $$

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n)),其中，n为问题规模，f(n)为语句关于n所占存储空间的函数。