时间复杂度的计算

野性酷女 2023-10-13 19:42 12阅读 0赞

> 时间复杂度的定义：算法的时间复杂度是一个数学函数，定量的描述该算法的运行时间，一个算法的所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

> 作用：主要衡量的是一个算法的运行速度。

> 表示方式：大O的渐进表达式

> 推导大O阶的方法
> 
> 1.用常数1取代运行时间中的所有加法常数，例子如下：
> 
> F(N)=3\*N^2+2\*N+10 => F(N)=3\*N^2+2\*N+1
> 
> 2.在修改后的运行次数中，只保留最高阶项，例子如下：
> 
> F(N)=3\*N^2+2\*N+1 => F(N)=3\*N^2
> 
> 3.如果最高阶项存在且不是1，则去除与之这个项数相乘的常数，得到的结果就是大O阶了，例子如下：
> 
> F(N)=3\*N^2 =>F(N)=N^2
> 
> 使用大O渐进表示法以后F(N)=3\*N^2+2\*N+10=>O(N^2)

> 推荐初学者阅读大话数据这本书！！！

例子1

void func1(int N) {
            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    count++;
                }
            }
            for (int k = 0; k < 2 * N; k++) {
                count++;
            }
            int M = 10;
            while ((M--) > 0) {
                count++;
            }
        }
        /*
         *func1基本操作执行了F(N) = N^2 + 2*N + 10
         *时间复杂度：O(N^2)
         **/

例子2

void func2(int N) {
            int count = 0;
            for (int k = 0; k < 2 * N; k++) {
                count++;
            }
            int M = 10;
            while ((M--) > 0) {
                count++;
            }
    
            System.out.println(count);
        }
         /*
         *func2的时间复杂度: O(N)
         * */

例子3

void func3(int N, int M) {
            int count = 0;
            for (int k = 0; k < M; k++) {
                count++;
            }
            for (int k = 0; k < N; k++) {
                count++;
            }
            System.out.println(count);
        }
        /*
         * func3的时间复杂度：O(M+N)
         * */

例子4

int binarySearch(int[] array, int value) {
            int begin = 0;
            int end = array.length - 1;
            while (begin <= end) {
                int mid = begin + ((end - begin) / 2);
                if (array[mid] < value)
                    begin = mid + 1;
                else if (array[mid] > value)
                    end = mid - 1;
                else
                    return mid;
            }
            return -1;
        }
        /*binarySearch的时间复杂度：
         * O(logN)
         **/

例子5

/*
         *计算阶乘递归factorial的时间复杂度:
         *O(N)
         *递归的时间复杂度=>递归的次数*每次递归后代码的执行次数
         *                    N            1 
         **/
        long factorial(int N) {
            return N < 2 ? N : factorial(N - 1) * N;
        }

例子6

/*
        * 计算斐波那契递归fibonacci的时间复杂度：
        * O(2^N)
        * */
        int fibonacci(int N){
            return N < 2 ? N:fibonacci(N-1)+fibonacci(N-2);
        }