如何衡量一个算法的好坏?

时间: 2023-08-28 admin IT培训

如何衡量一个算法的好坏?

如何衡量一个算法的好坏?

目录

一、前言

二、时间复杂度

三、空间复杂度


一、前言

算法是解决一类问题准确而完整的描述,它是程序设计的灵魂。如何衡量一个算法的好坏呢?是不是实现的代码越简洁算法越好呢?

算法在编写成可执行程序运行时,需要耗费时间资源和空间资源,因此衡量一个算法的好坏,是从时间和空间两个维度上衡量的,即时间复杂度和空间复杂度。

时间复杂度衡量一个算法运行的快慢;空间复杂度衡量一个算法运行所需要的额外空间。

二、时间复杂度

时间复杂度是一个函数,它定量描述了一个算法的运行时间。这个函数计算的是算法基本操作次数,并不是算法运行时间,因为在不同编译器下同一个算法有不同表现形式,而且我们不可能把所有算法都在编译器下实现。如下:

//计算Fun1的时间复杂度
void Fun1(int n)
{for (int i; i < n; i++){for (int j; j < n; j++){printf("Hi\n");}}int m = 100;while (m--){printf("Hello\n");}
}

根据时间复杂度的定义,我们很容易得出:Fun1的时间复杂度是n^2+100。然而在实际中,我们其实不必计算算法准确的执行次数,只要知道大概就行了,这里我们采用大O的渐进表示法。

大O的渐进表示法应用于时间复杂度和空间复杂度的计算,规则如下:

  1. 函数中的常数用1代替;
  2. 最终结果只保留函数的最高阶;
  3. 如果最高阶的系数不是1,系数就改成1。

使用大O的渐进表示法,Fun1的时间复杂度就是O(n^2)。

再看几个例子:

//计算二分查找算法的时间复杂度
int BinarySearch(int* arr, int len, int key)
{assert(arr);int left = 0;int right = len - 1;while (left <= right){int mid = (left + right) / 2;if (key < arr[mid]){right = mid - 1;}else if (key > arr[mid]){left = mid + 1;}else{return mid;}}return -1;
}

计算复杂度时,我们先不要着急看代码,先想一想算法实现的思路。

二分查找算法的最坏情况是找到最后只剩一个数时才找到,假设数组有N个数,第一次是在N个数中查找,第二次就是在N/2个数中查找,第三次就是在(N/2)/2中查找…以此类推,当最后只剩1个数时查找才会结束。设找了x次,则有N/(2^x)=1,即2^x=N, x=logN。二分查找算法的时间复杂度是O(logN)。

想想暴力查找时,最坏结果是遍历一遍数组才能找到,此时时间复杂度就是O(N),相比之下二分查找的O(logN) 更有优势。然鹅,二分查找有一个致命缺陷:必须在有序数组中进行。所以使用二分查找还得排序,而排序的最优时间复杂度是O(N*logN),综合之下,二分查找算法也不算多强了。

注:为了方便书写,在计算复杂度时,logN的底数为2时,底数2会被省略。

// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

在计算递归的时间复杂度时,只需要把每次递归调用的时间次数累加。Fac的时间复杂度是O(N).

三、空间复杂度

和时间复杂度类似,空间复杂度也是一个能定量描述算法运行额外空间的函数。

额外空间是指程序运行时显示申请的额外空间,函数运行时所需的栈空间在编译时就已经确定了。

举个栗子,计算上面阶乘递归函数Fac的空间复杂度。先说结果,Fac的空间复杂度是O(N)。因为每一次递归调用时,都要为递归调用的函数开辟一个新的空间,共有N次调用,故空间复杂度是O(N)。

递归调用的空间复杂度是将每次递归调用的变量个数累加,所以说,代码简洁算法效率不一定高,要谨慎使用递归,搞不好就有可能爆栈!

// 计算BubbleSort的空间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

乍一看,冒泡排序的循环里调用了Swap函数,那冒泡排序的空间复杂度应该是O(N^2),但联系到前面所说的“函数运行时所需的栈空间在编译时就已经确定了”,调用Swap函数的开销在函数运行前就确定了我们不难得出冒泡排序的空间复杂度只是O(N).


总结

  1. 计算复杂度时我们不需要精确的运行次数或者准确的额外运行空间,只要一个对整体复杂度计算影响最大的数。
  2. 随着计算机的发展,它的存储空间越来越大,如今我们已不再需要贴别关注空间复杂度。