一、数值极限
数值极限是指在一个单值数据集中,当取无限接近于某一数值时,该数据集的极限值。在数学中,极限的概念十分重要,以至于成为了微积分的核心概念。在编程中,我们也经常会使用到极限的概念。
例如,下面这段Python代码演示了如何通过二分查找算法求一个函数的极限值:
def f(x):
# 定义一个函数f
return x ** 2 + x - 1
def binary_search(f, l, r, eps):
# 定义二分查找算法
while r - l > eps:
mid = (l + r) / 2
if f(mid - eps) < f(mid + eps):
r = mid
else:
l = mid
return l
print(binary_search(f, -100, 100, 1e-6))
二、计算机存储极限
计算机在存储数字和其它数据时,也有着自己的极限。这主要是由于计算机使用二进制来存储数据,因此只能表示有限的数字。例如,使用双精度浮点数,计算机能够表示的最大数字为1.7976931348623157e+308。当需要表示更大的数字时,我们就需要使用多倍精度浮点数等更高级别的数据类型。
下面这段C++代码展示了如何使用多倍精度浮点数(long double)来计算e的值:
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long double e = 1.0, eps = 1e-18;
long double d = 1.0;
int i = 1;
while (d > eps) {
d /= i;
e += d;
i++;
}
cout << setprecision(20) << e << endl;
return 0;
}
三、时间极限
时间极限是指在一定的时间内,能够完成的最大计算量。这个极限与计算机的性能、算法的效率有关。例如,对于同一个问题,一个算法的时间复杂度为O(n),另一个算法的时间复杂度为O(n^2),那么前者的极限会高于后者,因为前者的运算速度更快。
下面这段Java代码展示了如何利用动态规划算法求解“最长公共子序列”问题:
public static void main(String[] args) {
String str1 = "ABCD";
String str2 = "ACDF";
int n = str1.length(), m = str2.length();
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
System.out.println(f[n][m]);
}
四、空间极限
空间极限是指在一定的内存空间内,能够处理的最大数据规模。这个极限与算法的数据结构、计算机的内存大小有关。例如,在处理图像数据时,如果图像数据过大,很容易导致内存爆满,这时就需要使用分块或部分读取的方法来解决。
下面这段Python代码演示了如何用一维数组来存储二维矩阵,并对其中的元素进行操作:
n, m = 4, 3 # 设定矩阵大小
a = [0] * n * m # 用一维数组存储二维矩阵
for i in range(n):
for j in range(m):
k = i * m + j # 计算下标
a[k] = i + j # 赋值
# 输出二维矩阵
for i in range(n):
for j in range(m):
k = i * m + j
print(a[k], end=' ')
print()