• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

了解时间复杂度

互联网 diligentman 2周前 (04-08) 7次浏览

1.算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.大o的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
用通俗的话来说就是一种估算。
eg:
F(N)=NN+N+2
用大o的渐进表示法就是O(N
N).
推导大O阶方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

eg:

void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
 ++count;
}
int M = 10;
while (M--)
{
 ++count;
}
printf("%dn", count);
}

F(N)=2*N+10,在这里我们认为2对结果的影响不大所以时间复杂度是O(N)。
eg:

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("%dn", count);
}

由于不清楚谁对结果的影响大,所以M和N都留下。
F(N)=M+N,时间复杂度是O(M+N).

void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
 ++count;
}
printf("%dn", count);
}

F(N)=100如果循环是常数的话,时间复杂度是O(1).
在时间复杂度的计算中,通常假设数组/字符串长度是N。
面对不确定的情况时默认时间复杂度最坏。
求冒泡排序的时间复杂度

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;
}
}

F(N)=N-1+N-2+N-3+…+1
时间复杂度是一个等差数列,O(N*N)
二分查找的时间复杂度

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;
}
}

最好的情况:o(1)
最坏的情况:
我们先逆着来看:122*…2=N
找了x次则/2了x次
2^x=N
x=log2^n
所以最坏的情况是O(log2^n)
递归算法的时间复杂度
递归算法的时间复杂度=递归次数
每次递归函数中的次数。

long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

后面讲解二叉树的时候会着重讲解。


程序员灯塔
转载请注明原文链接:了解时间复杂度
喜欢 (0)