
   void test(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++;
        }
        System.out.println(count);
    }

在计算时间复杂的度的时候我们会选择一直改变的量作为基本操作数。

上面的代码执行次数为F(N)=N^2+2N+10

其中N^2为嵌套的2个for循环，2N为另一个for循环，while循环M=10.

当F(N)中的N改变时，其中的执行次数也随之进行改变。

如F(10)=130

F(100)=10210

F(1000)=1002010

我们一般对于时间复杂度只需要计算大概，不需要精确计算，我们只需要用大O的渐进表示法来进行表示。

我们将上面的操作次数化简为大O来表示为F(N)=N^2+2N+10 ---> O(N^2)

(2)大O表示法的规则

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

（3）使用大O表示法来计算时间复杂度例子

1.二分查找的时间复杂度


    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;
    }

最终计算出二分查找的时间复杂度O（N）=log2n

2.递归的时间复杂度

（1）求阶乘的时间复杂度


//求阶乘
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}

（2）求斐波那契数列的时间复杂度


//求斐波那契数列
int fibonacci(int N) {
return N <=2 ? 1 : fibonacci(N-1)+fibonacci(N-2);
}

（4）时间复杂度的注意事项

一般我们考虑的是算法的最坏运行请情况。例如，对于一个普通的查找而言，我们考虑的是最坏找到某个元素运行次数。

三.空间复杂度

1.概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

2.例子

（1）计算非递归的空间复杂度

方法：计算在运行过程中创建了多少个变量

二分查找空间复杂度：

将斐波那契数列每位计算出来保存在数组中


long[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}

(2)递归的空间复杂度

方法：单次递归需要的空间*递归层数

四：总结

对于求时间复杂度的计算需要在平时多加练习，总结，对于不同的算法时间复杂度的计算方法不止上面这些，如果遇到可以记录下来，再进行总结，如果直接看不出来可以画图进行计算。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/508051