首页 > 编程知识 正文

算法的时间复杂度与什么有关,时间复杂度 主定理

时间:2023-05-05 18:38:37 阅读:191424 作者:4683

什么是算法时间复杂度 关于时间频度:一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个 算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n); 什么是算法空间复杂度 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。固定部分:这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。可变空间:这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。 算法时间复杂度如何计算

1、用常数1替代语句频度中所有的加法项
2、在(1)的结果中,只保留数的最高项
3、最高阶项若系数不为1,则去除系数(或是改为1)
在计算时间复杂度时,目的主要是逼近指令运算次数,所以可以在指令运行次数函数中,保留最高次项作为时间复杂度,例如5nn+2n+1 其时间复杂度可简化为O(n*n)

复杂算法时间复杂度如何计算 1. 主定理


翻译过来即为

在计算时间复杂度时主要通过 f(n)函数的幂数同以b为底a的log值作比较,分别来套公式,下面举几个例子:


参考链接:
添加链接描述
添加链接描述
添加链接描述
添加链接描述

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。