当前位置: 首页 > news >正文

中国做美国酒店的网站南山网站seo

中国做美国酒店的网站,南山网站seo,外贸网站怎么做效果好,无锡建设网站的公司哪家好文章目录 算法复杂度时间复杂度1. 定义2. 表示方法3. 常见时间复杂度4.案例计算分析冒泡排序二分查找斐波那契数列(递归法)斐波那契数列(迭代法) 空间复杂度案例分析冒泡排序斐波那契数列(递归法)斐波那契数…

文章目录

    • 算法
    • 复杂度
      • 时间复杂度
        • 1. 定义
        • 2. 表示方法
        • 3. 常见时间复杂度
        • 4.案例计算分析
            • 冒泡排序
            • 二分查找
            • 斐波那契数列(递归法)
            • 斐波那契数列(迭代法)
      • 空间复杂度
      • 案例分析
            • 冒泡排序
            • 斐波那契数列(递归法)
            • 斐波那契数列(迭代法)
      • 时间复杂度对比

正文

算法

算法(Algorithm):就是定义良好的计算过程,他取⼀个或⼀组的值为输⼊,并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤,⽤来将输⼊数据转化成输出结果。

​ 程序=数据结构+算法,一个好的程序需要有一个好的算法,那如何去衡量一种算法的好坏呢?这就需要我们计算算法的复杂度。

复杂度

​ 复杂度是计算机科学中的一个基础概念,它帮助我们理解和评估算法的效率,对于算法设计和优化至关重要。算法的复杂度通常分为时间和空间复杂度两个方面。

时间复杂度


1. 定义

​ 在计算机科学中,算法的时间复杂度是⼀个函数式T(N),它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率,那么为什么不去计算程序的运⾏时间呢?

​ 1.因为程序运⾏时间和编译环境和运⾏机器的配置都有关系,⽐如同⼀个算法程序,⽤⼀个⽼编译器进⾏编译和新编译器编译,在同样机器下运⾏时间不同。

​ 2.同⼀个算法程序,⽤⼀个⽼低配置机器和新⾼配置机器,运⾏时间也不同。

​ 3.并且时间只能程序写好后测试,不能写程序前通过理论思想计算评估。


2. 表示方法

​ 如定义所示,时间复杂度是一个函数式T(N),T(N)通过表示程序的指令的执行次数来定量描述程序的运行时间。

​ 例如,T(N)=10,T(N)=2N+10,T(N)=N2等等等,都是描述一个程序指令的执行次数

​ 但是,设想一下,采用这样的表示方法,如果两种算法一种T(N)=N2,另一种T(N)=N2+100,当N越大时二者差距就可以忽略不计,如果我们仍然这样表示,不免缺乏简洁性和统一性。

大O渐进表示法

​ 在这基础上,我们联想数学中所学的等阶无穷大概念,数学中使用小o来表示高阶无穷小,而采用大O来表示等阶无穷大。具体的来说,对于函数T(N),当N趋于无穷时,我们能否找到这样一个函数f(N),使得 T ( N ) f ( N ) \frac{T(N)}{f(N)} f(N)T(N)为一个常数,答案是可以的。


3. 常见时间复杂度

下面列出了一些常见时间复杂度O(N)的表示法,即f(N)的常见形式。

  • 常数时间复杂度:O(1),表示算法的执行时间不随输入规模的增长而变化,是最理想的情况。
  • 对数时间复杂度:O(log n),通常出现在二分查找等分治算法中。
  • 线性时间复杂度:O(n),表示算法的执行时间与输入规模成正比。
  • 线性对数时间复杂度:O(n log n),通常出现在快速排序、归并排序等分治算法中。
  • 平方时间复杂度:O(n2),通常出现在嵌套循环的算法中。
  • 指数时间复杂度:O(2n),通常出现在递归算法中。
  • 多项式时间复杂度:O(nk),k可能是大于 2 的正整数,这意味着算法在大规模数据上的性能下降较快。

4.案例计算分析
冒泡排序
// 计算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;}
}
  • 最好情况,若数组有序

​ T(N) =N

  • 最差情况,若数组与要求顺序反序

​ T(N) = N ∗ ( N − 1 ) 2 \frac{N*(N-1)}{2} 2N(N1)

有n个元素,需要排n-1趟,第i趟需要排n-i次

即(n-1)+(n-2)+……+1,结果如上所示

我们发现上述第一种是最好情况,而第二种是最坏情况,俗话说的好“做最好的准备,做最坏的打算”,所以很合理的我们应该将最坏的情况计算结果当做时间复杂度,上述即T[N]=N2


二分查找
// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;while (begin < end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid;elsereturn mid;}return -1;
}
  • 最好情况

    O(1)

  • 最坏情况

    O(logN)

    一次对半筛选,当数据很多时筛选k次才找到,2k=N,对数函数增长规律一样,为了保持统一性,下标可以忽略,建议写法即为logN。


斐波那契数列(递归法)
// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

在这里插入图片描述

以此类推,即为O(2N)。

斐波那契数列(迭代法)
long long  Fib(size_t n)
{int a = 1;int b = 1;int c = 1;while (n > 2){c = a + b;a = b;b = c;n--;}return c;
}
  • 可见我们使用迭代的方法,将时间复杂度降为了O(N)。

空间复杂度

类比时间复杂度,相似内容不再过多赘述了

  • 空间复杂度也是⼀个数学表达式,是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。

  • 空间复杂度不是程序占⽤了多少bytes的空间,因为常规情况每个对象⼤⼩差异不会很⼤,所以空间复杂度算的是变量的个数。

  • 注意:函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定!


案例分析

下面我们用具体案例来熟悉空间复杂度的计算

冒泡排序
// 计算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;}
}
  • 我们只申请了常数个变量,所以很显然空间复杂度为O(1)

斐波那契数列(递归法)
// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
  • 空间复杂度为O(N)
  • 当我们输入N时,第一步递归将会沿着N-1,N-2一直到3递推,在n为3这个函数栈帧里调用2和1,并返回给3注意此时1和2的函数栈帧已经销毁,以此类推,返回一个销毁一个,程序在执行时同一时刻实际使用的空间不会超过n个(即往下递推的深度),只是每个n值相同函数栈帧在不同时刻执行了一次又一次的销毁创建过程,即在时间复杂度里面我们所讨论的调用次数的问题,但在空间复杂度中我们只关心使用的空间,故为O(N)。

斐波那契数列(迭代法)
long long  Fib(size_t n)
{int a = 1;int b = 1;int c = 1;while (n > 2){c = a + b;a = b;b = c;n--;}return c;
}
  • 这个也很显而易见了,为O(1)。

时间复杂度对比

下面是常见时间复杂度对比

在这里插入图片描述

在这里插入图片描述

http://www.15wanjia.com/news/19449.html

相关文章:

  • 做网站java好还是.net好巨量引擎广告投放平台登录入口
  • 新疆气象局网站市场调研报告总结
  • 个人软件制作网站源码培训方案怎么做
  • 可以兼职做设计的网站软文营销广告案例
  • 电商网站 手续如何推广小程序平台
  • 百度做网站电话多少钱抖音seo是什么意思
  • 山东杰瑞数字做网站免费个人网站服务器
  • 移动网站怎么做优化百度关键词优化公司
  • 深圳网站建设外贸公司排名广东广州重大新闻
  • 网站开发与设计实训报告心得城市分站seo
  • ico网站图标网站建设公司企业网站
  • 江苏营销型网站推广产品推广方式有哪些
  • ppt设计网站seo外链平台
  • 网站建设相关推荐下载百度到桌面上
  • 深圳网站建设公司简介seo外包顾问
  • 郑州定制网站开发企业网站制作流程
  • 北京大学 讣告上海短视频seo优化网站
  • 天津做不锈钢的网站互联网优化是什么意思
  • 十个有创意的线上活动重庆seo整站优化设置
  • 佛山市网站建设分站企业国内新闻最新
  • 做网站文字要求网址大全名称
  • 手机怎么建立自己网站上海品牌推广公司
  • 一家专门做原型的网站长沙网站关键词推广
  • 大网站如何优化上海seo公司
  • 怎样做企业文化网站策划公司一般怎么收费
  • 企业如何在自己的网站上做宣传设计公司
  • 个人网站源码下载网站建站模板
  • 知名企业网站建设百度托管运营哪家好
  • 公司网页设计制作价格淘宝关键词优化技巧
  • html编辑器的推荐湖南seo网站开发