了解时间复杂度

1.算法效率

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

2.大o的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
用通俗的话来说就是一种估算。
eg:
F（N)=NN+N+2
用大o的渐进表示法就是O（NN）.
推导大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("%d\n", 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("%d\n", 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("%d\n", 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);
}

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