常见的算法复杂度及其示例（java版）

一、引言

    我们都知道，算法复杂度是用来评估算法性能的，在计算复杂度时，应当做出最差最不理想的估计，例如在循环遍历一个数组查找一个元素时，应当估计循环完全进行，这也称为算法运行的上界，在数据结构和算法中，以T表示算法性能（时间、复杂度），以O为常量，T=O(n)，n越大，表示复杂度越高。

二、常见的算法复杂度及其排序：

O(1) 
三、举例：
 
①、复杂度为O(1)的算法：判断数字n是否为偶数
 
    
    //判断数字n是否为偶数
    public static boolean isEven(int num){
        return num%2==0;
    }
 
 ②、复杂度为O(logn)的算法：求数字n的二进制位数
 
    //求数字n的二进制位数
    public static int sumDigits(int num){
        int digits=0;
        while(num!=0){
            digits++;
            num=num/2;
        }
        return digits;
    }
 
③、复杂度为O(√n)的算法：求数字n的所有约数
 
    
    //求数字n的所有约数。
    public static void getAllDivisor(int num){
        System.out.println("数字"+num+"的所有约数为：");
        for (int i=1;i<=Math.sqrt(num);i++){//例如当6除以二时，三也是6的余数，所以算到平方根
            if (num%i==0){
                if (num/i!=i){
                    //这里应该去除重复结果集，否则就会出现4的约数有 1,2,2,4这种情况。
                    System.out.println(i+" "+num/i);
                }else {
                    System.out.println(i+"");
                }
            }
        }
    }
 
④、复杂度为O(n)的算法：遍历一个一维数组
 
    
    //遍历一个一维数组
    public static  void foreachArry(){
        int a[]={1,2,3,4,56,9};
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
 
⑤、复杂度为O(2^n)的算法：求位数为n的所有二进制数
 
    
    //求长度为n的所有二进制数字
    public static void getAllBinNums(int num){
        List BinList=new ArrayList<>();//定义一个集合存放所有二进制数
        double count=Math.pow(2,num);//求出一共多少个二进制数，用于循环
        for (int i=0;i 
⑥、复杂度为O(n!)的算法：求长度为n的数组元素的所有排列顺序
 
    
    //求长度为n的数组的所有排列顺序个数
    public static void countSort(int size){
        int count=1;
        for (int i = size; i > 0; i--) {
            count=count*i;
        }
        System.out.println(count);
    }
 
⑦、复杂度为O(n^2)的算法：遍历一个n*n的二维数组（这里以三为例）
 
    
    //遍历一个n*n的二维数组,这里以三为例。
    public static void foreachTwoArray(){
        int a[][]=new int[][]{{1,2,3},{4,5,6},{7,8,9}};//定义一个二维数组（一个数组里有n个以m个元素个数的一维数组）
        for (int n=0;n<3;n++){//二维数组长度
            for (int m=0;m<3;m++){//一维数组长度
                System.out.print(a[n][m]+" ");
            }
            System.out.println("n");
        }
    }