[C语言] 数据结构-算法效率的度量方法-事前分析估算方法

事前分析估算方法:在计算机程序编制前,依据统计方法对算法进行估算,抛开与计算机硬件软件有关的因素,一个程序的运行时间,依赖于算法的,好坏和问题的输入规模,所谓问题输入规模是指输入量的多少

推导过程,比如计算1+2+3+...100:

int i,sum=0,n=100 //执行1次

for(i=1;i<=n;i++) //执行n+1次

{

sum=sum+i; //执行n次

}

去掉头尾循环判断,执行了n次

第二种算法:

int sum=0,n=100 //执行1次

sum=(1+n)*n/2; //执行1次

去掉头尾循环判断,执行了1次

延伸一下:

int i,x,j,sum=0,n=100 //执行1次

for(i=1;i<=n;i++) //执行n+1次

{

for(j=1;i<=n;j++){

x++;

sum=sum+x; //执行n*n次

}

}

循环部分的代码整体需要执行n^2次

因此当问题输入规模是n时,f(n)作为一个函数操作数量分别为

f(n)=n

f(n)=1

f(n)=n^2

由于函数的渐进增长,n的值越大,差异也就越大,因此我们在判断一个算法时

一般都忽略掉常数项,忽略掉次要项,只关注最高次项,关注最高阶项的阶数

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏雪之梦技术驿站

go 学习笔记之go是不是面向对象语言是否支持面对对象编程?

面向对象编程风格深受广大开发者喜欢,尤其是以 C++, Java 为典型代表的编程语言大行其道,十分流行!

9240
来自专栏Golang开发

RDD操作——文件数据读写

要加载本地文件,必须采用“file:///”开头的这种格式。执行上上面这条命令以后,并不会马上显示结果,因为,Spark采用惰性机制,只有遇到“行动”类型的操作...

12650
来自专栏木又AI帮

【leetcode刷题】T146-二叉树的层平均值

https://leetcode-cn.com/problems/average-of-levels-in-binary-tree

8360
来自专栏奔跑的人生

[Spring cloud 一步步实现广告系统] 15. 使用开源组件监听Binlog 实现增量索引准备

执行sql update ad_user set user_status=1 where user_id=10;

9320
来自专栏dylanliu

设计模式之策略模式

策略模式(Strategy Pattern)隶属于设计模式中的行为型模式,是日常开发中使用最广的一个模式,相对于其他模式,自认为这个模式是最容易理解和使用的。

6720
来自专栏ICT售前新说

服务器中的网络虚拟化

今天聊的网络虚拟化和前面几期文章中提到的Fabric上SDN中实现的网络虚拟化还不一样,此处网络虚拟化是指在服务器内部如何为虚机提供联通和通向外网时...

15210
来自专栏木又AI帮

【leetcode刷题】T147-两数之和 IV - 输入 BST

https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst

6220
来自专栏机器之心

ICCV 2019 | 解读北大提出的期望最大化注意力网络EMANet

本文介绍笔者被 ICCV 2019 接受为 Oral 的论文 Expectation-Maximization Attention Networks for S...

34620
来自专栏须臾之余

算法之时间复杂度&几种排序算法探究 顶

归并排序的细节讲解与复杂度分析 时间复杂度O(N*logN),额外空间复杂度O(N)

12060
来自专栏木又AI帮

【leetcode刷题】T145-根据二叉树创建字符串

https://leetcode-cn.com/problems/construct-string-from-binary-tree

8320

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励