时间复杂度：执行算法所需要的时间

空间复杂度：执行算法所需要的内存空间

时间复杂度的定义：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数

  • 通常将O(1)、O(n)、O(logn)、O(n2)等分别叫做常量阶、线性阶、对数阶、平方阶等
  • 推导大O阶方法：1.用常数1取代运行时间中的所有加法常数；2.修改后的运行次数函数中，值保留最高阶项；3.如果最高阶向存在且不是1，则去除与这个项相乘的常数
  • 常数阶O(1)：
1
2
3
int sum=0，n=100；
sum=（1+n）*n/2;
System.out.println(sum);
  • 线性阶O(n):
1
2
3
for(int i=0;i<n;i++){
//O(1)的算法
}
  • 对数阶O(logn):
1
2
3
4
5
int num=1;
while(num<n){
num=num*2;
//O(1)的算法
}
  • 平方阶O(n^2):
1
2
3
4
5
for(int i=0;i<n;i++){
    for(int j=i;j++){
    //O(1)的算法
    }
}
  • 常用的时间复杂度按照耗费的时间从小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)