算法效率是评估算法性能的关键指标。时间复杂度，用大O表示法表示，是描述算法运行时间的函数。
简单来说，时间复杂度就是一个函数，与其他函数所不同，它是用大写的 O 来表示的，比如说 O(1)、O(n)、O(log n) 等等。时间复杂度用来定性描述该算法的运行时间，强调定性表示，即描述大致的运行时间趋势。
让我们看一张时间复杂度的图，列举了常见的几种时间复杂度。需要关注的是 O(1)、O(log n)、O(n)、O(n^2) 这几种。你要明白它们的大小关系，比如说 n^2 比 n 大，n 比 log n 大，log n 比 1 大。
让我们通过几段简单的代码来理解时间复杂度
1. 首先是一个 O(1) 的例子：常数时间
function exampleO1(arr) {
return arr[0];
}
解释：
这个例子是一个常数时间复杂度的算法。函数 exampleO1 接收一个数组 arr 作为参数，然后立即返回数组的第一个元素 arr[0]。无论输入数组的规模有多大，函数的执行时间都是恒定的。这是因为函数只执行一次数组访问操作，与输入规模无关，没有循环或其他影响执行时间的结构。因此，这个算法的时间复杂度是 O(1)。
2. 再看一个 O(n) 的例子： 线性时间
function linearTime(arr) {
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
}
解释：
这个例子展示了一个线性时间复杂度的算法。函数 linearTime 接收一个数组 arr 作为参数，然后通过 for 循环遍历整个数组，逐个打印数组元素。随着输入数组规模 n 的增加，循环执行的次数也线性增加。因此，这个算法的时间复杂度是 O(n)。
如果你先执行一个时间复杂度为 O(x) 的代码，然后接着执行一个线性时间复杂度的 for 循环（O(n)），整体的时间复杂度是 O(x + n)。在计算时间复杂度时，如果两个时间复杂度先后排列，我们将它们相加，取增长趋势更快的时间复杂度。
3. 再来看一个 O(log n) 的例子：对数时间
function binaryExponential(n) {
let i = 1;
while (i < n) {
i *= 2;
}
}
解释：
这个例子展示了一个对数时间复杂度的算法。函数 binaryExponential 接收一个参数 n，然后通过 while 循环，不断将变量 i 乘以 2，直到 i 大于等于 n。循环体内执行的次数是 log n，因为它在求 2 的多少次方等于 n。因此，这样的代码时间复杂度是 O(log n)。
对数时间复杂度通常在有序数据的查找中出现，比如二分查找算法。
4. 最后我们来看下O(N²) - 平方级增长
function quadraticTime(arr, n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(arr[i], arr[j]);
}
}
}
解释：
这个例子展示了一个平方级增长的算法，时间复杂度为 O(N²)。函数 quadraticTime 接收一个数组 arr 和一个参数 n，然后通过嵌套的两个循环遍历整个数组。由于两个循环的迭代次数都是 n，总的执行次数是 n 乘以 n，即 N²。这样的算法在处理规模为 N 的输入时，执行时间随输入规模的平方级增长。
通过以上例子，我们更深入地理解了算法的时间复杂度。这种理解从常数到线性，再到对数，展现了代码运行时的规律。
示例练习：
1. 多变量循环
function variableLoop(N, M) {
let count = 0;
for (let k = 0; k < M; k++) {
count++;
}
for (let k = 0; k < N; k++) {
count++;
}
console.log(count);
}
解释
这个算法的时间复杂度为 O(N+M)，因为我们无法确定 N 和 M 哪一个更大。算法包含两个循环，一个循环执行 M 次，另一个执行 N 次，因此整体时间复杂度是它们的和。
2. 字符串查找
function findCharacter(str, c) {
while (str !== '') {
if (str[0] === c) {
return str;
}
str = str.slice(1);
}
return null;
}
解释：
这个字符串查找算法的时间复杂度为 O(N)，其中 N 是字符串的长度。在最坏情况下，需要遍历整个字符串，直到找到目标字符或遍历结束。
3. 冒泡排序
function bubbleSort(arr, n) {
for (let end = n; end > 0; end--) {
let exchange = 0;
for (let i = 1; i < end; i++) {
if (arr[i - 1] > arr[i]) {
swap(arr, i - 1, i);
exchange = 1;
}
}
if (exchange === 0)
break;
}
}
解释：
冒泡排序的时间复杂度为 O(N²)，其中 N 是数组的长度。算法通过嵌套的循环，对数组进行多次比较和交换，使得整体的时间复杂度为 N 的平方级别。
3. 二分查找
function binarySearch(arr, n, x) {
let begin = 0;
let end = n - 1;
while (begin < end) {
let mid = begin + ((end - begin) >> 1);
if (arr[mid] < x)
begin = mid + 1;
else if (arr[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
解释：
二分查找的时间复杂度为 O(log₂N)，其中 N 是数组的长度。该算法通过不断缩小搜索范围，将查找的时间复杂度降低到对数级别。
3. 递归
function fibonacci(N) {
return N < 2 ? N : fibonacci(N - 1) + fibonacci(N - 2);
}
解释：
递归算法的时间复杂度为 O(2^N)，其中 N 是输入的参数。这是因为递归算法反复调用自身，导致指数级别的增长，效率相对较低。
总结
通过这些例子，能够更深入地理解算法的时间复杂度，从而更好地评估和选择合适的算法以提高程序的性能。
网友评论