时间复杂度分析

2021-12-12 04:48:48

一般情况下，一秒之内相应时间复杂度的算法能解决的数据规模

时间复杂度实验

如何正确的判断算法的时间复杂度

时间复杂度实验：每次将数据规模提高两倍，看时间的变化，以此来验证算法的时间复杂度

以下为代码实例：

测试算法，分别为二分查找O（logN），查找最大值（O（N）），归并排序（O（NlogN））

package com.ice.time;

import static java.lang.Math.min;

public class MyAlgorithmTester {

    // O(logN),二分法查找
    public static int binarySearch(int arr[], int n, int target) {

        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == target) return mid;
            if (arr[mid] > target) r = mid - 1;
            else l = mid + 1;
        }
        return -1;
    }

    // O(N),从数组中寻找最大值
    public static int findMax(int arr[], int n) {

        assert (n > 0);

        int res = arr[0];
        for (int i = 1; i < n; i++)
            if (arr[i] > res)
                res = arr[i];

        return res;
    }

    // O(NlogN) 归并排序
    private static void __merge(int arr[], int l, int mid, int r, int aux[]) {

        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = aux[j];
                j++;
            } else if (j > r) {
                arr[k] = aux[i];
                i++;
            } else if (aux[i] < aux[j]) {
                arr[k] = aux[i];
                i++;
            } else {
                arr[k] = aux[j];
                j++;
            }
        }
    }

    public static void mergeSort(int arr[],int n){
        int[] aux = new int[n];
        for(int i = 0;i<n;i++){
            aux[i] = arr[i];
        }
        for(int sz = 1;sz<n;sz+=sz){
            for(int i = 0;i<n;i+=sz+sz){
                __merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1),aux);
            }
        }
        return;
    }
}

工具类，生成随机数组或有序数组，用于测试算法

package com.ice.time;

public class MyUtil {

    public static int[] generateRandomArray(int n, int rangeL, int rangeR) {
        assert (n > 0 && rangeL <= rangeR);

        int arr[] = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * (rangeR - rangeL) + rangeL);
        }
        return arr;
    }

    public static int[] generateOrderedArray(int n) {

        int arr[] = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        return arr;
    }
}

Main函数，测试算法用的时间并打印，观察时间就可以推测算法的时间复杂度

package com.ice.time;

import static java.lang.Math.pow;

public class Main {
    public static void main(String[] args){
        for(int i =10;i<=24;i++){
            int n = (int) pow(2,i);
            int[] arr = MyUtil.generateRandomArray(n,0,100000000);

            long startTime=System.currentTimeMillis();
            MyAlgorithmTester.selectionSort(arr,n);
            long endTime=System.currentTimeMillis();//记录结束时间
            
            System.out.print("data size 2^"+i+" = "+n);
            System.out.println("\tTime cost:"+(double)((endTime-startTime)/1000));
        }
    }
}