|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
第003讲:算法的时间复杂度
知识点回顾:
0. 本节视频
1. 算法效率的度量
通常度量一个算法的执行效率,有两种方法,一种是事前分析法,一种事后分析法。
后者很好理解,正所谓真金不怕火炼,事实胜于雄辩。直接让程序跑起来,然后对它进行计时,算法好坏咱们拿测试结果说话。
但事后分析法是不是适合算法效率的度量呢?
答案是不合适的!
算法的执行效率受到硬件性能、编程语言选择和输入数据的显著影响:
- 高性能的计算机能够迅速处理同一算法,而性能较差的机器则可能需要更长时间
- 使用接近底层的编程语言如 C 或汇编实现的算法,通常比使用高级语言如 Python 或 JavaScript 实现的算法执行更快
- 算法的性能取决于输入数据的大小和特性,不同的输入对结果影响至关重要
2. 什么是时间复杂度呢?
算法的时间复杂度,是衡量算法执行时间如何随输入数据规模的增长而变化的一种度量方式。
它表达了算法执行时间的大致趋势,而不是精确的执行时间。
时间复杂度通常用大 O 符号表示,称为大 O 记法。
3. 实例演示如何计算时间复杂度
代码一:
- #include <stdio.h>
- #include <string.h>
- void printFirstCharacter(char* str) {
- printf("%c", str[0]);
- }
- int main() {
- char str[] = "FishC";
- printFirstCharacter(str);
- return 0;
- }
复制代码
代码二:
- #include <stdio.h>
- void printLastCharacter(char* str) {
- int i = 0;
- while (str[i] != '\0') {
- i++;
- }
- printf("%c", str[i - 1]);
- }
- int main() {
- char str[] = "FishC";
- printLastCharacter(str);
- return 0;
- }
复制代码
代码三:
- #include <stdio.h>
- // 使用迭代的方式进行二分查找
- int binarySearch(int arr[], int left, int right, int x)
- {
- while (left <= right) {
- int mid = left + (right - left) / 2;
- // 检查x是否在中点
- if (arr[mid] == x)
- return mid;
- // 如果x大于中点,忽略左半部分
- if (arr[mid] < x)
- left = mid + 1;
- // 如果x小于中点,忽略右半部分
- else
- right = mid - 1;
- }
- // 在数组中不存在x
- return -1;
- }
- int main(void)
- {
- int arr[] = {2, 3, 4, 10, 40, 55, 77, 88, 99};
- int n = sizeof(arr) / sizeof(arr[0]);
- int x = 10;
- int result = binarySearch(arr, 0, n - 1, x);
- (result == -1) ? printf("数组中不存在该元素\n")
- : printf("元素在数组中的索引为 %d\n", result);
- return 0;
- }
复制代码
代码四:
- #include <stdio.h>
- int main() {
- int n = 100;
- int x = 1;
- while (x < n) {
- x = x * 3;
- }
- return 0;
- }
复制代码
代码五:
- #include <stdio.h>
- int main() {
- int n = 100;
- for(int i = 1; i <= n; i++) {
- int x = 1;
- while (x < i) {
- x = x * 2;
- }
- }
- return 0;
- }
复制代码
代码六:
- #include <stdio.h>
- int main() {
- int n = 100;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < n; j++) {
- printf("i: %d, j: %d\n", i, j);
- }
- }
- return 0;
- }
复制代码
代码七:
- #include <stdio.h>
- // 冒泡排序函数
- void bubbleSort(int arr[], int n) {
- // 外层循环,遍历每一个元素
- for(int i = 0; i < n-1; i++) {
- // 内层循环,从第一个元素开始,比较相邻的两个元素
- for (int j = 0; j < n-i-1; j++) {
- // 如果前一个元素大于后一个元素,则交换他们
- if (arr[j] > arr[j+1]) {
- int temp = arr[j];
- arr[j] = arr[j+1];
- arr[j+1] = temp;
- }
- }
- }
- }
- // 打印数组的函数
- void printArray(int arr[], int size) {
- for (int i = 0; i < size; 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]);
- bubbleSort(arr, n);
- printf("排序后的数组: \n");
- printArray(arr, n);
- return 0;
- }
复制代码
4. 思维导图
|
|