赞
踩
如何衡量一个算法的好坏呢?比如对于以下斐波那契数列:
long long Fib(int N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何衡量其好与坏呢?
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般
是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢,通常用大 O O O符号表示,表示最坏情况下的时间复杂度。
而空间复杂度主要衡量一个算法运行所需要的额外空间,也用大 O O O符号表示,表示最坏情况下的空间复杂度。
在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计
算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
因此,一个好的算法应该尽可能地减少时间复杂度,使程序更加高效。
在分析算法时间复杂度时,通常需要考虑算法的基本操作次数,即算法执行的基本步骤的数量。
在常见的算法中,常见的基本操作包括赋值、比较、循环、递归等。通过计算基本操作的次数,可以得到算法的时间复杂度。
常见的时间复杂度有:
时间复杂度 | 排序 |
---|---|
O ( 1 ) O(1) O(1) | 1 |
O ( log n ) O(\log n) O(logn) | 2 |
O ( n ) O(n) O(n) | 3 |
O ( n log n ) O(n\log n) O(nlogn) | 4 |
O ( n 2 ) O(n^2) O(n2) | 5 |
O ( n 3 ) O(n^3) O(n3) | 6 |
O ( 2 n ) O(2^n) O(2n) | 7 |
O ( n ! ) O(n!) O(n!) | 8 |
O ( n n ) O(n^n) O(nn) | 9 |
时间复杂度 | 执行次数 (n=10000) |
---|---|
O ( 1 ) O(1) O(1) | 1 |
O ( log n ) O(\log n) O(logn) | 14 |
O ( n ) O(n) O(n) | 10000 |
O ( n log n ) O(n \log n) O(nlogn) | 133333 |
O ( n 2 ) O(n^2) O(n2) | 100000000 |
O ( n 3 ) O(n^3) O(n3) | 1000000000000 |
O ( 2 n ) O(2^n) O(2n) | 2^10000 |
O ( n ! ) O(n!) O(n!) | 10000! |
其中,常数阶的时间复杂度最小,为 O ( 1 ) O(1) O(1),而指数阶和阶乘阶的时间复杂度非常大,通常需要避免使用。注:下文详细介绍 |
注:通常情况下,对数阶时间复杂度 O ( log n ) O(\log n) O(logn)是以2为底的对数,也就是以 O ( log 2 n ) O(\log_2 n) O(log2n)表示。这是因为在算法中常用的是以2为底的对数,例如在二分查找算法中,每次可以将搜索区间缩小一半,因此需要进行 l o g 2 n log_2 n log2n次操作才能完成搜索。因此,我们通常默认对数阶时间复杂度是以2为底的对数。
但是,在一些特殊的场景中,对数阶时间复杂度也可以使用其他底数的对数表示。例如,在信息论中,常用的是以自然对数e为底的对数,因此有时候也会用 O ( l o g e n ) O(log_e n) O(logen)来表示对数阶复杂度。不过,这种情况比较少见,通常我们默认对数阶复杂度是以2为底的对数。
时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。
一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。
但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。
一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。
Func1 执行的基本操作次数 : F ( N ) = N 2 + 2 ∗ N + 10 F(N)=N^{2}+2 * N+10 F(N)=N2+2∗N+10
N = 10 F ( N ) F(N) F(N) = 130
N = 100 F ( N ) F(N) F(N) = 10210
N = 1000 F ( N ) F(N) F(N) = 1002010
实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,
那么这里我们使用大 O O O的渐进表示法。
大 O O O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大 O O O阶方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大 O O O阶。
使用大 O O O的渐进表示法以后,Func1的时间复杂度为: O ( N 2 ) O(N^{2}) O(N2)
N = 10 F ( N ) F(N) F(N) = 100
N = 100 F ( N ) F(N) F(N) = 10000
N = 1000 F ( N ) F(N) F(N) = 1000000
通过上面我们会发现大 O O O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)
例如:在一个长度为N数组中搜索一个数据x
最好情况:1次找到
最坏情况:N次找到
平均情况:N/2次找到
在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为 O ( N ) O(N) O(N)
// 计算Func2的时间复杂度?
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
该函数的时间复杂度为 O ( N ) O(N) O(N),可以用思维导图表示为:
Func2(N)
|
|----> for (int k = 0; k < 2 * N; ++k) // 执行2N次
| |
| |----> ++count
|
|----> while (M--) // 执行10次,与N无关
| |
| |----> ++count
|
|----> printf("%d\n", count) // 执行1次
其中,for循环执行了 2 N 2N 2N次,while循环执行了10次,printf语句执行了1次。
因此取最高阶去掉相乘的常数,该函数的时间复杂度为 O ( N ) O(N) O(N)。
这时有人就会问为什么时间复杂度不是 O ( 2 N ) O(2N) O(2N)呢?
这里我们举一个生活中的例子来说明:
当我们想要煮一锅粥时,我们需要先将水烧开,然后将米放入水中煮熟。假设我们想要煮一锅N杯米的粥,我们可以:
虽然第一种方法需要加入的次数是第二种方法的两倍,但是它们的时间复杂度是相同的,都是 O ( N ) O(N) O(N)。
因为随着粥量的增加,加入米的次数的增长趋势与粥量增加的趋势相同,都具有线性增长的特点。
换句话说,不管我们每次加入多少杯米,所需的时间复杂度都是与粥量成正比的,即 O ( N ) O(N) O(N)。
这就是常数因子可以被忽略的原因,我们只关心算法时间复杂度随着数据规模增长时的增长趋势,而不关心具体的常数因子。
再举个例子:假设你现在要做绿皮火车从广州到杭州,可能需要20小时,但是做只需高铁6-7小时,也许你觉得快了10多个小时有点区别。如果是到火星呢?甚至到太阳系以外的地方呢?那是不是两者并没有任何区别。所以年轻人格局要打开,胸怀天下,胸怀宇宙!
// 计算Func3的时间复杂度?
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}
for (int k = 0; k < N; ++k)
{
++count;
}
printf("%d\n", count);
}
对于给定的函数 Func3
,可以分析其时间复杂度如下:
综上所述, Func3
函数的时间复杂度为
O
(
N
+
M
+
1
)
O(N+M+1)
O(N+M+1)。由于常数项 1 可以被忽略,因此该函数的时间复杂度为
O
(
N
+
M
)
O(N+M)
O(N+M)。
// 计算Func4的时间复杂度?
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
对于给定的函数 Func4
,我们可以看到,该函数只包含一个 for 循环和一个 printf 函数。
由于该循环的执行次数是一个固定的常数 100,不会随着输入规模 N N N 的增加而增加,因此该循环的时间复杂度是 O ( 1 ) O(1) O(1) 。
// 计算Func4_的时间复杂度?
void Func4_(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count+N);
}
该函数与原函数 Func4
的不同之处在于,在 printf 函数中加上了一个常数 N。
由于该常数不会随着输入规模 N 的增加而增加,因此该常数对函数的时间复杂度没有影响。
因此,该函数的时间复杂度仍然是 O ( 1 ) O(1) O(1)。
// 计算strchr的时间复杂度?
const char* strchr(const char* str, int character) {
while (*str)
{
if (*str == character)
return str;
else
str++;
}
}
strchr
函数是一个C语言中的字符串处理函数,用于在一个字符串中查找一个特定字符的第一次出现位置,
并返回该位置到字符串末尾的剩余部分。
使用示例:
int main()
{
const char* str = "hello world";
const char* p = strchr(str, 'l');
if (p != NULL)
printf("找到第一次所在位置 %d: %s\n", p - str, p);
return 0;
}
对于 strchr
函数的时间复杂度,可以分析如下:
该函数的时间复杂度是 O ( n ) O(n) O(n),其中 n n n是输入字符串的长度。因为该函数的实现是使用一个循环逐个遍历字符串中的字符,
直到找到目标字符或者到达字符串的末尾为止。因此,当输入字符串很长时,该函数的执行时间也会相应地增加。
需要注意的是,在某些特定情况下,strchr
函数的时间复杂度可能会更低,例如当输入字符串中的目标字符在字符串开头或者不在字符
串中时。但是在一般情况下(以最坏的结果,或者你可以用木桶原理进行类比),我们可以认为 strchr
函数的时间复杂度是
O
(
n
)
O(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; } }
冒泡排序算法:它的核心思想是通过不断交换相邻的元素,将待排序的序列中的最大值不断“冒泡”到序列的末尾。
具体而言,该算法包含一个外层 for 循环和一个内层 for 循环。
外层循环控制待排序序列的长度,每次循环会将待排序的序列中的最大值移到末尾。
内层循环用于比较相邻的两个元素并进行交换,以便将最大值不断“冒泡”到序列的末尾。
当n个数进行冒泡排序时,最坏情况下需要进行 n − 1 n-1 n−1 趟排序。在每一趟排序中,要比较 n − i n-i n−i 次,
因此总的比较次数为 ∑ i = 1 n − 1 i = 1 + 2 + ⋯ + ( n − 2 ) + ( n − 1 ) = ( n + 1 ) ( n − 1 ) 2 \sum_{i=1}^{n-1} i = 1 + 2 + \dots + (n-2) + (n-1) = \frac{(n+1)(n-1)}{2} ∑i=1n−1i=1+2+⋯+(n−2)+(n−1)=2(n+1)(n−1)次,即时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
// 计算BinarySearch的时间复杂度? int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; // [begin, end]:begin和end是左闭右闭区间,因此有=号 while (begin <= end) { int mid = begin + ((end - begin) >> 1); if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid - 1; else return mid; } return -1; }
该代码实现了二分查找算法,其时间复杂度为 O ( log n ) O(\log n) O(logn)。下面是该算法时间复杂度的分析:
这时大家可能觉得比较抽象,我们具体举个例子:
假设有一个有序数组 a a a,长度为 n n n,我们需要查找其中的元素 x x x。
下面我们以 a = [ 1 , 3 , 5 , 7 , 9 ] a=[1, 3, 5, 7, 9] a=[1,3,5,7,9] 和 x = 5 x=5 x=5 为例,演示二分查找算法的运行过程。
begin=0
,end=4
。mid=2
,比较中间位置的元素
a
[
m
i
d
]
a[mid]
a[mid] 和目标元素
x
x
x,发现
a
[
m
i
d
]
>
x
a[mid]>x
a[mid]>x,因此将终止位置设置为中间位置的上一个元素,即 end=mid-1=1
。mid=0
,比较中间位置的元素
a
[
m
i
d
]
a[mid]
a[mid] 和目标元素
x
x
x,发现
a
[
m
i
d
]
<
x
a[mid]<x
a[mid]<x,因此将起始位置设置为中间位置的下一个元素,即 begin=mid+1=1
。mid=1
,比较中间位置的元素
a
[
m
i
d
]
a[mid]
a[mid] 和目标元素
x
x
x,发现
a
[
m
i
d
]
=
x
a[mid]=x
a[mid]=x,因此找到目标元素,返回其下标 mid=1
。在上述例子中,我们进行了三次查找操作,即使数组长度增加到 n = 100 n=100 n=100,也只需要进行 7 次查找操作。因此,二分查找算法的时间复杂度为 O ( log n ) O(\log n) O(logn)。
log n \log n logn 可以用公式表达为: log 2 n \log_2 n log2n,表示以 2 为底数的对数运算。例如,当 n = 8 n=8 n=8 时, log 2 8 = 3 \log_2 8=3 log28=3,表示有 8 个元素的有序数组最多只需要进行 3 次查找操作即可找到目标元素。
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
该递归实现的阶乘函数的时间复杂度为 O ( N ) O(N) O(N)。
每次调用递归函数都会将规模缩小一,直到规模为 1 1 1,然后不断返回并相乘,总共需要进行 N N N 次递归调用。
因此,总的时间复杂度为 O ( N ) O(N) O(N)。
以如下代码举例:
void Print(int n) //1234 { if (n > 9) { Print(n / 10);//123 12 1 } printf("%d ", n % 10); } int main() { int num = 0; scanf("%d", &num); Print(num); return 0; }
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
if (0 == N)
return 1;
for (int i = 0; i < N; i++)
{
//...
}
return Fac(N - 1) * N;
}
每次for循环过后是一个等差数列,从N一直递减至0。循环n次,执行递归n次;循环n-1次,执行递归n-1次 ;如下图所示
因此总的比较次数为 ∑ i = 1 n i = 1 + 2 + ⋯ + ( n − 2 ) + ( n − 1 ) + n = ( n + 1 ) n 2 \sum_{i=1}^{n} i = 1 + 2 + \dots + (n-2) + (n-1)+n = \frac{(n+1)n}{2} ∑i=1ni=1+2+⋯+(n−2)+(n−1)+n=2(n+1)n次,即时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是?
int closest_sum(int arr[], int N, int sum) { int i = 0; //开始位置 int j = N - 1; // 末尾 int closest = arr[i] + arr[j]; // 初始化最接近sum的值为数组的第一个和最后一个元素的和 while (i < j) { int cur_sum = arr[i] + arr[j]; if (cur_sum == sum) return cur_sum; // 如果找到了和sum相等的一对元素,则直接返回它们的和 else if (abs(cur_sum - sum) < abs(closest - sum)) closest = cur_sum; // 如果当前和更接近sum,则更新最接近sum的值 if (cur_sum < sum) // 如果当前和小于sum,则增加a的值,即将i向右移动一位 i++; else // 如果当前和大于sum,则减小b的值,即将j向左移动一位 j--; } return closest; }
该算法的时间复杂度是 O ( N ) O(N) O(N),其中 N N N是数组中元素的个数。在最坏情况下,要遍历整个数组。
// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
该Fib递归函数的时间复杂度为指数级别,具体来说是 O ( 2 n ) O(2^n) O(2n)。这是因为每一次递归调用都会导致两个新的递归调用,
因此递归树(二叉树)的深度为N,每个节点有两个子节点,所以递归树的节点数为 2 N 2^N 2N。
而每个节点的计算时间为常数级别(都是已知的为2个子节点),因此总时间复杂度为 O ( 2 N ) O(2^N) O(2N)。
以下是对该时间复杂度的分析:
由于 Fib数列的定义是每个数等于前两个数之和,因此递归函数中每次调用自己都会导致两个新的递归调用,即:
Fib(N) = Fib(N-1) + Fib(N-2)
以下是对递归树的图表:
Fib(N)
/ \
Fib(N-1) Fib(N-2)
/ \ / \
Fib(N-2) Fib(N-3) Fib(N-3) Fib(N-4)
/ \ / \ / \ / \
... ... ... ... ... ...
在递归树中,每个节点表示Fib数列中的一个值,每个节点的左子节点表示前一个Fib数,右子节点表示前两个Fib数。
递归树的深度为N,每个节点有两个子节点,因此递归树的节点数为 2 N 2^N 2N。
实例1基本操作执行了2N+10次,通过推导大 O O O阶方法知道,时间复杂度为 O ( N ) O(N) O(N)
实例2基本操作执行了M+N次,有两个未知数 M M M和 N N N,时间复杂度为 O ( N + M ) O(N+M) O(N+M)
实例3基本操作执行了10次,通过推导大 O O O阶方法,时间复杂度为 O ( 1 ) O(1) O(1)
实例4基本操作执行最好1次,最坏N次,时间复杂度一般看最坏,时间复杂度为 O ( N ) O(N) O(N)
实例5基本操作执行最好N次,最坏执行了 ( N − 1 ) ∗ ( N + 1 ) / 2 (N-1)*(N+1)/2 (N−1)∗(N+1)/2次,通过推导大 O O O阶方法+时间复杂度一般看最坏,时间复杂度为 O ( N 2 ) O(N^2) O(N2)
实例6基本操作执行最好1次,最坏O(logN)次,时间复杂度为$ O(logN)$
ps: l o g N logN logN在算法分析中表示是底数为2,对数为 N N N。有些地方会写成 l g N lgN lgN。上文有介绍为什么是以2为底
实例7通过计算分析发现基本操作递归了 N N N次,时间复杂度为 O ( N ) O(N) O(N)。
实例8通过计算分析发现基本操作递归了 2 n 2^n 2n次,时间复杂度为 O ( 2 n ) O(2^n) O(2n)。(建议画递归栈帧的二叉树)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。