第003讲：算法的时间复杂度
第003讲：算法的时间复杂度知识点回顾：
0. 本节视频
https://www.bilibili.com/video/BV1MX4y1p7ud?p=3
1. 算法效率的度量
通常度量一个算法的执行效率，有两种方法，一种是事前分析法，一种事后分析法。
后者很好理解，正所谓真金不怕火炼，事实胜于雄辩。直接让程序跑起来，然后对它进行计时，算法好坏咱们拿测试结果说话。
但事后分析法是不是适合算法效率的度量呢？
答案是不合适的！
算法的执行效率受到硬件性能、编程语言选择和输入数据的显著影响：
[*]高性能的计算机能够迅速处理同一算法，而性能较差的机器则可能需要更长时间
[*]使用接近底层的编程语言如 C 或汇编实现的算法，通常比使用高级语言如 Python 或 JavaScript 实现的算法执行更快
[*]算法的性能取决于输入数据的大小和特性，不同的输入对结果影响至关重要
2. 什么是时间复杂度呢？
算法的时间复杂度，是衡量算法执行时间如何随输入数据规模的增长而变化的一种度量方式。
它表达了算法执行时间的大致趋势，而不是精确的执行时间。
时间复杂度通常用大 O 符号表示，称为大 O 记法。
3. 实例演示如何计算时间复杂度
代码一：
#include <stdio.h>
#include <string.h>
void printFirstCharacter(char* str) {
printf("%c", str);
}
int main() {
char str[] = "FishC";
printFirstCharacter(str);
return 0;
}
**** Hidden Message *****
代码二：
#include <stdio.h>
void printLastCharacter(char* str) {
int i = 0;
while (str != '\0') {
i++;
}
printf("%c", str);
}
int main() {
char str[] = "FishC";
printLastCharacter(str);
return 0;
}
**** Hidden Message *****
代码三：
#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 == x)
return mid;
// 如果x大于中点，忽略左半部分
if (arr < 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);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("数组中不存在该元素\n")
: printf("元素在数组中的索引为 %d\n", result);
return 0;
}
**** Hidden Message *****
代码四：
#include <stdio.h>
int main() {
int n = 100;
int x = 1;
while (x < n) {
x = x * 3;
}
return 0;
}
**** Hidden Message *****
代码五：
#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;
}
**** Hidden Message *****
代码六：
#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;
}
**** Hidden Message *****
代码七：
#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 > arr) {
int temp = arr;
arr = arr;
arr = temp;
}
}
}
}
// 打印数组的函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr);
bubbleSort(arr, n);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
**** Hidden Message *****
4. 思维导图
度量一个算法的执行效率可以用事前分析法或事后分析法。事后分析法就是执行一遍程序，用事实说话，其虽然简单，结果却会因机器性能、编程语言、输入数据的不同而出现较大差异，故算法效率的度量通常采用事前分析法，即在不执行程序的情况下分析出算法的效率。为此引出“时间复杂度”的重要概念，以衡量算法执行时间如何随输入数据规模的增长而变化，表达算法执行时间的大致趋势。时间复杂度通常用大O符号表示，称为大O记法。视频以几个较为典型的算法为例，分析了这些算法的时间复杂度。从中可以看出，计算时间复杂度并不需要求出精确的结果，只需要求出算法大致的数据规模，且通常只关注“大格局”，也即程序最耗时（随问题规模n增长最快，幂次最高）的部分。 n趋于正无穷时：O(1)<O(logn)<O(nlogn)<O(n^2)
页:
[1]