举例说明时间复杂度与空间复杂度

什么是时间复杂度与空间复杂度？相信很多人对时间复杂度与空间复杂度的了解处于懵懂状态，小编给大家总结了以下内容。如下资料是关于复杂度与空间复杂度的内容。

网站建设哪家好，找创新互联建站！专注于网页设计、网站建设、微信开发、微信小程序定制开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了新建免费建站欢迎大家使用！

1、时间复杂度

      所谓时间复杂度实际上就是函数，既是函数计算执行的基本操作次数。ps:这里的函数是指数学里面的函数，而不是C语法里的函数。

      如下面这个代码：

void Test1 ( int N )

{

           for (int i = 0; i < N ; ++ i)

          {

                    for (int j = 0; j < N ; ++ j)

                   {

                              //...

                   }

          }

           for (int k = 0; k < 2 * N ; ++ k)

          {

                    //...

          }

           int count = 10;

           while (count --)

          {

                    //...

          }

}

所以这段代码的时间复杂度是： F(N) = N^2 + 2N + 10，这个时间计算的就是时间复杂度。

• 算法分析的分类

1. 最坏情况：任意输入规模的最大运行时间。（上界）

2. 平均情况：任意输入规模的期望运行时间。

3. 最好情况：任意输入规模的最小运行时间，通常最好情况不会出现。（下界）

例如：在一个长度为N的线性表中搜索一个数据x。

最坏情况:N次比较。

平均情况:N/2次比较。

最好情况:1次比较。

在实际中我们通常情况考量的是算法的最坏运行情况。也就是说对于任意输入规模N，算法的最长运行时间，理由如下：

1. 一个算法的最坏情况的运行时间是在任意输入下的运行时间上界。

2. 对于某些算法，最坏的情况出现的较为频繁。

3. 大体上看，平均情况与最坏情况一样差。

算法分析要保持大局观：

1. 忽略掉那些的常数。

2. 关注运行时间的增长趋势，关注函数式中增长最快的表达式。

• O的渐进表示法（Big O Notation）

通常我们使用O记号法表示最坏运行情况的渐进上界。其实也就是说我们使用O标记法表示时间复杂度，一般关注的是算法运行的最坏情况。

下面我们使用大O的渐进表示法计算下面函数的时间复杂度

如：F(N) = N^3 + N^2 + N +1000,则关注N^3->O(N^3)

• 【1.一般算法的时间复杂度计算】

void Test1 ( int N )

{

           for (int i = 0; i < N ; ++ i)

          {

                    for (int j = 0; j < N ; ++ j)

                   {

                              //...

                   }

          }

           for (int k = 0; k < 2 * N ; ++ k)

          {

                    //...

          }

           int count = 10;

           while (count --)

          {

                    //...

          }

}

Test1的时间复杂度为：O(N^2)

void Test2 (int N, int M)

{

           for (int i = 0; i < M ; ++i)

          {

          }

           for (int k = 0; k < N ; ++k)

          {

                    //...

          }

}

Test2的时间复杂度为：O(M+N)

void Test3 (int N, int M)

{

           for (int i = 0; i < M ; ++i)

          {

                    for (int j = 0; j < N ; ++j)

                   {

                              //...

                   }

          }

}

Test3的时间复杂度为：O(M*N)

【2.递归算法的时间复杂度计算】

递归算法的时间复杂度为递归总次数*每次递归次数。

• 空间复杂度

空间复杂度的计算跟时间复杂度类似，也使用大O的渐进表示法。--（对象的个数）

要注意的是递归算法的空间复杂度，假如递归深度为N*每次递归的空间大小为1，则空间复杂度为O(N)。

 以斐波那契数列为例：

#include<iostream>

#include<stdlib.h>

using namespace std;

//斐波那契数列的递归算法(一般解法)

int Fib(int N )

{

             return N < 2 ? N : Fib( N - 1) + Fib( N - 2);

}

int main()

{

             int ret=Fib(0);

            cout << ret << endl;

            system( "pause");

             return 0;

}

此代码的空间复杂度是：O（N），既是深度。

             时间复杂度是：O（2^N）.

这段代码有下面几个明显缺陷：

1、递归时会有函数的压栈开销。

2、有重复计算。

    所以我们需要对这段代码进行优化。请看下面：

方法一：可以倒着计算，定义三个变量，如下所示：

long long Fib(size_t N )

{

             long long * Fibarray = new long long[ N + 1];

            Fibarray[0] = 0;

            Fibarray[1] = 1;

             for ( int i = 2; i <= N; ++i)

            {

                        Fibarray[i] = Fibarray[i - 1] + Fibarray[i - 2];

            }

             long long ret = Fibarray[ N];

             delete[] Fibarray;

             return ret;

}

此方法的时间复杂度为：O（N）。

            空间复杂度为：O（N）。

方法二：用一个循环开辟一个数组。

long long Fib(size_t N )

{

             long long Fib[3] = { 0, 1, N };

             for ( int i = 2; i <= N; ++i)

            {

                        Fib[2] = Fib[1] + Fib[0];

                        Fib[0] = Fib[1];

                        Fib[1] = Fib[2];

            }

             return Fib[2];

}

这种方法的时间复杂度是：O（N）。

       空间复杂度是：O（1），因为常数个对象。

看完上诉内容，你们对时间复杂度与空间复杂度大概了解了吗？如果想了解更多相关文章内容，欢迎关注创新互联行业资讯频道，感谢各位的阅读！

名称栏目：举例说明时间复杂度与空间复杂度
URL链接：https://www.cdcxhl.com/article36/gppdpg.html

成都网站建设公司_创新互联，为您提供商城网站、服务器托管、全网营销推广、企业建站、动态网站、网站收录

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联