场景1：T(n) = 2

int hello() {

    System.out.println("Hello, World!\n");      //  需要执行 1 次

    return 0;       // 需要执行 1 次

}

 

场景2：T(n) = n + 1 + n = 2n + 1

int hello(int n) {

   for(int i=0; i<n; i++) {                                          // 需要执行 (n + 1) 次

       System.out.println("Hello, World!\n");      //  需要执行 n 次

   }

    return 0;       // 需要执行 1 次

}

 

场景3：T(n) = n + 1 + n  + n+ 1+(2n+1)*n  + n*n = 3n*n + 4n + 2 (n*n)

int hello(int n) {

   for(int i=0; i<n; i++) {                                          // 需要执行 (n + 1) 次

       System.out.println("Hello, World!\n");      //  需要执行 n 次

   }

 for(int i=0; i<n; i++) {                                          // 需要执行 (n + 1) 次

      for(int j=0; j<n; j++) // 需要执行 (2n + 1)*n 次

         System.out.println("Hello, World!\n");      //  需要执行 n*n次

   }

    return 0;       // 需要执行 1 次

}

 

大 O记号

T(n)，即算法为求解规模为n的问题，所需要执行的指令操作次数

反映了随着问题规模增长，计算成本如何增长

渐进分析：在问题规模足够大后，计算成本如何增长？

 

Big O

重点考察增长趋势

大O定义：

存在常数 c 和函数 f(n)，使得当 n >= c 时 T(n) <= f(n)，表示为：T(n) = O(f(n))

它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述

 O(f2(n))

 

与T(n)相比，f(n)更加简洁，但是依然能够反应增长趋势

常数项可忽略： O(f(n)) = O(c * f(n)), O(f(n)) = O(c + f(n))

低次项可忽略： O(na+nb) = O(na), a > b > 0

如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))

算法的执行次数：T(n) = n + 1 + n  + n+ 1+(2n+1)*n  + n*n = 3n*n + 4n + 2

复杂度：O(f(n))= O(n*n)

 

场景1：T(n) = n+1+1 = n+2

复杂度：O(n)

void aFunc(int n) {

    for(int i = 0; i < n; i++) {         

        printf("Hello, World!\n");      

    }

}

 

场景2：T(n) = n +n^2 + n^2= 2n^2+2

复杂度：O(n^2)

void aFunc(int n) {

    for(int i = 0; i < n; i++) {         

        for(int j = 0; j < n; j++) {       

            printf("Hello, World!\n");      

        }

    }

}

 

场景3：T(n) = n+1+1 = n+2 + 2n^2+2

复杂度：O(n^2)

void aFunc(int n) {

    for(int i = 0; i < n; i++) {

        for(int j = 0; j < n; j++) {

            printf("Hello, World!\n");

        }

    }

    for(int j = 0; j < n; j++) {

        printf("Hello, World!\n");

    }

}

 

场景4：复杂度O(n^2)

void aFunc(int n) {

    if (n >= 0) {

         for(int i = 0; i < n; i++) {

            for(int j = 0; j < n; j++) {

                printf("输入数据大于等于零\n");

            }

        }

    } else {

         for(int j = 0; j < n; j++) {

            printf("输入数据小于零\n");

        }

    }

}

 

场景5：T(n) = 2lgn

复杂度：O(lgn)

16*16*4

void aFunc(int n) {

    for (int i = 2; i < n; i++) {

        i *= 2;

        printf("%i\n", i);

    }

}

 

场景6：T(N) = T(N-1) + T(N-2) (复杂度是多少？）

long aFunc(int n) { //Fab

    if (n <= 1) {

        return 1;

    } else {

        return aFunc(n - 1) + aFunc(n - 2);

    }

}

 

其他记号

 

复杂度分析-递归与主定理

在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由Jon Bentlery，Dorothea Haken和James B. Saxe在1980年提出，在那里被描述为解决这种递推的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen，Leiserson，Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。

 

以下是评估递归时间复杂度的主定理，例如有递归形式

T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)

其中, a≥1a≥1和b≥1b≥1, 均为常数, f(n)f(n)是一个确定的正函数。 在f(n)f(n)的三类情况下, 我们有T(n)T(n)的渐近估计式：

1. 若对于某常数ε>0ε>0, 有f(n)=O(nlogba−ε)f(n)=O(nlogba−ε), 则T(n)=Θ(nlogba)T(n)=Θ(nlogba)

2. 若f(n)=O(nlogba)f(n)=O(nlogba), 则T(n)=O(nlogba∗lgn)T(n)=O(nlogba∗lgn)

3. 若对某常数ε>0ε>0, 有f(n)=Ω(nlogba+ε)f(n)=Ω(nlogba+ε), 且对常数c<1c<1 与所有足够大的nn,有af(n/b)≤cf(n)af(n/b)≤cf(n), 则T(n)=Θ(f(n))T(n)=Θ(f(n))。

 

主定理示例

快速排序: T[n] = 2T[n/2] + O(n)

 对比主定理， T [n] = aT[n/b] + f (n)

快速排序中：a = 2, b = 2, f(n) = O(n)

故其复杂度为：平均的复杂度O(nlogn)

最坏：o(n^2)

 

常数阶O(1)

Int sum(int n) {

  Int sum = 0;

  for(int i=1; i<=n; i++){  // O(n)

    sum+=I;

    return sum;

  }

}

Int sum(int n) {

   return n*(n+1)/2;  // O(1)

}

 

对数阶O(logn)

多项式阶O(nc)

指数阶O(2n)

几种不同类型的时间复杂度

最好情况时间复杂度（best case time complexity）O(1)

最坏情况时间复杂度（worst case time complexity）O(n)

平均情况时间复杂度（average case time complexity）O(n)

均摊时间复杂度（amortized time complexity）

ArrayList 可动态扩容的一个数组

Add: O(1)

当扩容时，需要O(n)

N*O(1) + O(n) = O(1)

下面我们看一下案例：

int search(int[] a, int target) {

   for(int j=0; j<a.length; j++){

          if(a[j] == target){

               return j;

          }

          return -1;

   }

}

1*1/n + 2*1/n + …. N*1/n =O(n)

 

空间复杂度

空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度就是 O(1)、O(n)、O(n^2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到

 

O(1)

Void reverseArray(int a[])

{

For(int i=a.length -1,j=0; I > j; i>=0; j++, i--) a[j] = a[i];

}

 

最后，我们可以尝试一下做一个任务哦，做完了可以和博主交流！