php家具网站模版,wordpress 浏览量 点击,山东省建设协会网站首页,wordpress 主题 数据库1. 时间复杂度
时间复杂度衡量的是算法运行时间与输入规模之间的关系。它通常用大O记号#xff08;Big O Notation#xff09;表示#xff0c;例如 O(1)、O(n)、O(n2) 等。
衡量方法#xff1a; 常数时间复杂度 O(1)#xff1a;无论输入规模如何#xff0c;算法的执行时…1. 时间复杂度
时间复杂度衡量的是算法运行时间与输入规模之间的关系。它通常用大O记号Big O Notation表示例如 O(1)、O(n)、O(n2) 等。
衡量方法 常数时间复杂度 O(1)无论输入规模如何算法的执行时间是固定的。 线性时间复杂度 O(n)算法的执行时间与输入规模成正比。 平方时间复杂度 O(n2)算法的执行时间与输入规模的平方成正比。 对数时间复杂度 O(logn)算法的执行时间与输入规模的对数成正比。
2. 空间复杂度
空间复杂度衡量的是算法运行过程中额外占用的内存空间与输入规模之间的关系。它也用大O记号表示。
衡量方法 常数空间复杂度 O(1)算法运行过程中只占用固定数量的额外空间。 线性空间复杂度 O(n)算法运行过程中占用的额外空间与输入规模成正比。 平方空间复杂度 O(n2)算法运行过程中占用的额外空间与输入规模的平方成正比。 示例C语言程序
示例1线性搜索时间复杂度 O(n)空间复杂度 O(1)
#include stdio.hint linearSearch(int arr[], int n, int target) {for (int i 0; i n; i) { // 遍历数组时间复杂度 O(n)if (arr[i] target) {return i; // 找到目标值返回索引}}return -1; // 未找到目标值返回 -1
}int main() {int arr[] {10, 20, 30, 40, 50};int n sizeof(arr) / sizeof(arr[0]);int target 30;int result linearSearch(arr, n, target);if (result ! -1) {printf(Element found at index %d\n, result);} else {printf(Element not found\n);}return 0;
}
分析 时间复杂度O(n)因为算法需要遍历整个数组。 空间复杂度O(1)因为算法只使用了常量级的额外空间变量 i 和 result。 示例2冒泡排序时间复杂度 O(n2)空间复杂度 O(1)
#include stdio.hvoid bubbleSort(int arr[], int n) {for (int i 0; i n - 1; i) { // 外层循环 n-1 次for (int j 0; j n - i - 1; j) { // 内层循环 n-i-1 次if (arr[j] arr[j 1]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp; // 交换相邻元素}}}
}void printArray(int arr[], int n) {for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);printf(Original array: );printArray(arr, n);bubbleSort(arr, n);printf(Sorted array: );printArray(arr, n);return 0;
}
分析 时间复杂度O(n2)因为算法包含两层嵌套循环。 空间复杂度O(1)因为算法只使用了常量级的额外空间变量 i、j 和 temp。 示例3递归实现的斐波那契数列时间复杂度 O(2n)空间复杂度 O(n)
#include stdio.hint fibonacci(int n) {if (n 1) {return n; // 基本情况}return fibonacci(n - 1) fibonacci(n - 2); // 递归调用
}int main() {int n 10;printf(Fibonacci number at position %d is %d\n, n, fibonacci(n));return 0;
}
分析 时间复杂度O(2n)因为递归树的深度为 n每个节点都有两个分支。 空间复杂度O(n)因为递归调用栈的最大深度为 n。 总结 时间复杂度衡量算法的运行时间通常用大O记号表示。 空间复杂度衡量算法运行过程中占用的额外内存空间也用大O记号表示。 在实际开发中时间和空间复杂度需要综合考虑以选择最适合问题的算法。
