Java算法之时间复杂度和空间复杂度的概念和计算

什么是时间复杂度和空间复杂度

时间复杂度是指算法执行所需要的时间，它通常使用大O符号来表示。在一个算法中执行基本操作的次数取决于输入的大小，所以通常我们将时间复杂度表示为输入大小n的函数。

空间复杂度是指算法执行所需的内存空间。空间复杂度也是一个随着输入大小n变化的函数，通常也使用大O符号来表示。

两者都是用来衡量算法的效率，可以用来比较不同算法的优劣。

如何计算时间复杂度和空间复杂度

时间复杂度的计算

在计算时间复杂度时，我们需要找到算法中执行时间最长的那段代码，然后根据其执行次数来确定时间复杂度。一般来说，常见的时间复杂度从小到大依次为O(1)、O(logn)、O(n)、O(nlogn)和O(n^2)。

下面举两个例子：

例1：

给定一个有序数组nums和一个目标值target，返回target在数组中的下标，如果不存在返回-1。

public static int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

我们可以看到，这个算法的执行时间主要是在while循环中的代码，对于一个长度为n的数组，每次循环都将数组的长度缩小一半，所以总共需要循环logn次，因此该算法的时间复杂度为O(logn)。

例2：

给定一个整数n，请计算从1到n的所有整数的和。

public static int sum(int n) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}

这个算法的执行时间主要是在for循环中的代码，它需要执行n次，因此该算法的时间复杂度为O(n)。

空间复杂度的计算

在计算空间复杂度时，我们需要找到算法中使用内存最大的那个变量或数据结构，并根据其存储空间来确定空间复杂度。

下面举一个例子：

例3：

给定一个整数n，请生成一个包含1到n²的所有整数的矩阵。

public static int[][] generateMatrix(int n) {
    int[][] res = new int[n][n];
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    int cnt = 1;
    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++) {
            res[top][i] = cnt++;
        }
        for (int i = top + 1; i <= bottom; i++) {
            res[i][right] = cnt++;
        }
        if (top < bottom && left < right) {
            for (int i = right - 1; i >= left; i--) {
                res[bottom][i] = cnt++;
            }
            for (int i = bottom - 1; i > top; i--) {
                res[i][left] = cnt++;
            }
        }
        top++;
        bottom--;
        left++;
        right--;
    }
    return res;
}

可以看到，这个算法最占用内存的变量是二维数组res，它占用了n²个空间，因此该算法的空间复杂度为O(n²)。

总结

本文介绍了时间复杂度和空间复杂度的概念和计算方法，并且通过两个例子分别展示了如何计算时间复杂度和空间复杂度。对于算法的设计和选择，时间复杂度和空间复杂度都是非常重要的考虑因素，可以帮助我们衡量不同算法的优劣，优化算法的效率。