时间复杂度&空间复杂度

算法的时间复杂度和空间复杂度统称为算法的复杂度。

时间复杂度

• 时间复杂度实际上是一个函数，该函数计算的是执行基本操作的次数。
  算法存在最好、平均和最坏情况：
  最坏情况：任意输入规模的最大运行次数（上界）
  平均情况：输入任意规模的期望运行次数
  最好情况：任意输入规模的最小运行次数，通常最好情况不会出现下界（下界）

  eg：在一个长度为N的线性表中搜索一个数据X
  最坏情况：N次比较
  平均情况：N/2次比较
  最好情况：1次比较

在实际情况下通常关注算法的最坏的运行情况，因此使用O渐进表示法来计算算法的时间复杂度。

一般算法O(n)计算方法：

1.用常数1取代表达式中所有加法常数；
2.保留最高阶项；
3.最高阶项系数化为1。

分治算法的时间复杂度

分治算法的时间复杂度.png

递归算法的时间复杂度

时间复杂度=递归的总次数*每次递归的次数

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。【创建变量 调用函数（函数调用栈） malloc 栈】

对于一个算法来说，空间复杂度和时间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

有时我们可以用空间来换取时间以达到目的。

---

---

实现斐波那契数列(三种方法)

1 1 2 3 5 8 13 21 34 55...

递归

时间复杂度：O(2^N)
空间复杂度：O(N)

long long Fib(int n)
{
    if (n < 3)
        return 1;
    return Fib(n - 1) + Fib(n - 2);
}

int main()
{
    printf("%d\n",Fib(10));
    return 0;
}

尾递归

时间复杂度：O(N)
空间复杂度：O(N) or 编译器优化仅开辟一块空间O(1)

long Fib(long first, long second, long n)
{
    if (n < 3)
        return 1;
    if (3 == n)
        return first + second;
    return Fib(second, first + second, n - 1);
}
int main()
{
    printf("%d\n",Fib(1,1,10));
    return 0;
}

循环结构

时间复杂度：O(1)
空间复杂度：O(1)

int Fib(int n)
{
    int First = 1;
    int Second = 1;
    int ret = 1;
    int i = 3;
    for (i = 3; i <= n; i++)
    {
        ret = First + Second;
        First = Second;
        Second = ret;
    }
    return ret;
}

int main()
{
    printf("%d\n",Fib(10));
    return 0;
}