时间复杂度.md

算法分析神器

时间复杂度

https://mp.weixin.qq.com/s?__biz=MzU1MDE4MzUxNA==&mid=2247483867&idx=1&sn=6270b56b79cb74334eb4faf80de05f0a&scene=21#wechat_redirect

• O(n):

int n=100;
for (int i = 0; i < n ; i++){
    System.out.println("Test");

一般来说，最内层执行次数最多的语句就决定了整个算法的趋势。你只要看看最内层的语句执行次数的规律就行了，这个内层打印语句随着问题规模n的增加会呈线性增加，直接就可以判定复杂度为O(n)

• O（n^2）

int n=10;
for (int i = 0; i < n ; i++){
    for (int j = 0; j < n ; j++)
        System.out.println("Test");
        

那么按照这个方法就很容易得出下面这个嵌套的两层for循环的复杂度为O（n^2）了

• O(logn) 对数函数的趋势显然比线性函数好(对数函数随着自变量的增大因变量增长的很慢)

int n=10;
int sum = 1;
while (sum < n){
   sum = sum * 2;

每循环一次，sum就给自身乘以2，乘了多少次就跳出循环了呢(大于等于n)？不知道，就设为x吧，那么2^x=n,解出x=logn，这说明随着n的增大，最消耗时间的内层语句是呈对数变化的