时间复杂度学习笔记

    一直以来对时间复杂度这个概念理解不透，网上的文章太多，但大多比较难懂。最近在读《大话数据结构》，终于找到一个能看得明白的解释了，好记性不如烂笔头，索性记录一下。
    一般来说，常见的时间复杂度有o(1)常数阶,o(n)线性阶,o(n²)平方阶等。 那么一个算法的时间复杂度是怎么分析出来的呢？先上点概念，下面是推导方法（大O阶方法）

1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
如此以上三条得到的结果就是上面说的o(1),o(n)等时间复杂度。

下面直接上代码举例
1、常数阶o(1)

public void sum(){
  int sum = 0,int n = 100; //执行一次
  sum = (n+1) * n / 2; //执行一次
  System.print.out(sum); //执行一次
}

以上这段代码的运行次数函数是f(n)=3（次），根据上面的理论，先把3换成1，这段代码还是执行了3次，并且它并不会因为n的变化而导致执行次数发生改变，然后发现它根本没有最高结项，时间复杂度并没有o(2),o(3)这种说法。所以这个算法的时间复杂度就是o(1)。

2、线性阶o(n)

int n = 100;//执行一次
for(int i = 0;i < n; i++){
  System.print.out(sum); //这行代码一共被执行了100次（由于n是100，所以一共执行n次）
}

以上这段代码的运行次数函数是f(n)=n+1（次）,它会随着n的改变而改变执行次数。时间复杂度是不考虑常量的，所以这段算法的时间复杂度是就是o(n)。

…未完待续