C语言中算法时间复杂度_百度知道
C语言中算法时间复杂度
设n为正整数，请用大O表示法描述下列程序段的时间复杂度 x=91;y=100; while(y&0) { if(x&100) { x-=10; y--; } else x++; }
此题是一个双重循环。对于每个y值（y&0)，if语句执行11次，其中10次执行x++。因此，if语句的频度为11×100=1100次。 请问频度1100次是如何算出的？前面的执行11次，其中10次执行x++;这句我理解。但后面的频率11×100=1100次是如何得出的。为什么要这样算。请讲解下，谢谢
提问者采纳
看看循环体的个数，一般来说循环体越多 时间复杂度越高 例如for(i:0-&n) for(j: 0 -& m){ m += } 这段代码的操作执行次数是n*m
如果n和m之间有函数关系，如 n = 2m。基本操作次数就是2m^2，时间复杂度中只取最高次幂项且忽略系数，所以时间复杂度为：O(m^2) 当然也可以西城O(n^2)。
其他类似问题
时间复杂度的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁C语言写程序时 出现的时间复杂度 具体是什么意思？_百度知道
C语言写程序时 出现的时间复杂度 具体是什么意思？
这东西详细手打有点，去帮你找了个讲的比较详细的。 哪不懂可以追问 简单理解，时间复杂度就是执行语句被调用了多少次。(1)如果只调用了一次，如：x=5;if(x&-4) {x=x+4;} else {x=x+3;}在大括号中的内容，只会调用一个语句，那么O(n)=1;(2)如果调用了两次，如：x=5;if(x&-4) {x=x+4;} else {x=x+3;}x=x+56;在大括号中的内容，只会调用一个语句，但是在最后，还有一个计算公式要调用语句；总共加起来就是调用2次。那么O(n)=2;（3）用1个FOR循环调用for(x=0;x&n;x++){x=x+1;}x会从0到n-1循环，执行的语句就是将当前x值加入新的x中，总共调用n次；那么O(n)=n;(4）用2个嵌套FOR循环调用for(x=0;x&n;x++){
for(y=1;y&=n;y++)
{x=x+y;}}遇到嵌套循环，可以先将外面的FOR语句中的变量固定为初始值x=0，主要看里面的FOR语句的时间复杂度，很明显，里面语句执行次数是从1到n总共调用n次，O(n)=n；这还只是x=0时的调用。x可以从0到n-1，共n次。每次调用都会执行n次调用y的情况，因此，执行语句x=x+y；总共会调用n*n次。O(n)=n^2。 数执行语句的执行次数，就是时间复杂度。注意：(1)找到正确的执行语句。(2)for循环中的初始值和终止值。
for(i=0;i&n;i++) i值变化是从0到n-1，共n次。
for(i=0;i&=n;i++) i值变化是从0到n，共n+1次。(3)注意for循环的调用顺序，从里面到外面进行的。
其他类似问题
按默认排序
其他4条回答
数据结构没学吧 算法的执行时间依赖于具体的软硬件环境，所以，不能用执行时间的长短来衡量算法的时间复杂度，而要通过基本语句执行次数的数量级来衡量。　　求解算法的时间复杂度的具体步骤是：　　⑴ 找出算法中的基本语句；　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。　　⑵ 计算基本语句的执行次数的数量级；　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。　　⑶ 用大Ο记号表示算法的时间性能。　　将基本语句执行次数的数量级放入大Ο记号中。　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：　　for (i=1; i&=n; i++)　　x++;　　for (i=1; i&=n; i++)　　for (j=1; j&=n; j++)　　x++;　　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。　　常见的算法时间复杂度由小到大依次为：　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。
在C语言中主要有算法时间复杂度和算法空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，计算法执行过程中 的所需要的基本运算次数；算法的空间复杂度是一般指执行这个算法所需要的内存空间。
时间复杂度是用来描述算法优劣的手段，以执行一条简单的语句的时间为单位（记作O(1)）所以for(int i=0;i&n;i++){a++;}的时间复杂度为O(n)一般一个算法的时间复杂度取决于循环的嵌套层数和循环的次数
时间复杂度就是运行命令的多少，往往和循环联系在一起 两成循环嵌套，比如外层3里层4，那么运行的条数就是3*4
时间复杂度的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁C语言常用算法分析_百度百科
特色百科用户权威合作手机百科
收藏 查看&C语言常用算法分析本词条缺少概述，补充相关内容使词条更完整，还能快速升级，赶紧来吧！ISBN4装&&&&帧平装印刷日期
印次：1-1本书共分为4篇，第1篇为算法基础篇，包括程序之魂——算法、数据结构基础、查找与排序算法、基本算法思想等内容；第2篇为常用算法篇，包括数学算法、矩阵与数组问题、经典算法等内容；第3篇为趣味算法篇，包括数学趣题、逻辑推理题等内容；第4篇为算法竞技篇，包括计算机等级考试算法实例、程序员考试算法实例、信息学奥赛算法实例等内容。
本书提供了大量的自学视频、源程序、素材，提供了相关的模块库、案例库、素材库、题库等多种形式的辅助学习资料，还提供迅速及时的微博、QQ、论坛等技术支持。
本书内容详尽，实例丰富，非常适合作为零基础人员的学习用书和大中专院校师生的学习教材，也适合作为相关培训机构的师生和软件开发人员的参考资料。算法被称为程序设计的灵魂，也是学习编程的必备知识，因此被许多高等院校计算机专业列为必修课程。一个优秀的程序需要合理的数组组织和高效清晰的算法，这也是程序设计要研究的主要内容。
本书根据算法学习的步骤编排章节。全书共分为4篇，第1篇为算法基础篇，介绍了学习算法需要掌握的一些基础知识，包括程序之魂——算法、数据结构基础、查找和排序方法、基本算法思想等部分；第2篇为常用算法篇，列举了在编程中经常用到的一些算法，使读者了解一些常用算法的实现方法，包括数学算法、矩阵与数组问题、经典算法等算法；第3篇为趣味算法篇，列举了一些经典的趣味算法，能够激起大家的学习兴趣，在趣味中掌握算法精髓，包括数学趣题、逻辑推理题等算法；第4篇为算法竞技篇，通过不同的类型的算法实例使大家了解实战算法，包括计算机等级考试算法实例、程序员考试算法实例、信息学奥赛算法实例等内容。
为了更清晰地阐述算法和给出算法的设计思路，本书设置了以下栏目：
? 算法说明
对算法的具体要求和实现的功能进行说明。
? 算法分析
根据算法要求及要实现的功能进行分析，详细介绍实现的思路和方法。
? 实现过程
通过程序来实现算法，给出具体的实现过程和实现算法的完整代码。
本书具有以下特点。
* 循序渐进
本书从算法基础讲起，介绍算法的基本知识和常用的算法思想，逐层深入，由浅入深。
* 举例丰富
列举了程序设计和应用中的常用算法，使读者能够通过各种算法的学习而掌握实际开发的思路。
* 趣味实用
本书专门添加了趣味算法篇，列举生活中的一些趣味算法，使读者能够更有兴趣地学习，在娱乐中进步。
* 竞技实战
本书添加了各种计算机考试的算法实例，使读者在实战中提升。
本书配套资源
本书提供了内容丰富的配套资源，包括自学视频、源程序、素材，以及模块库、案例库、题库、素材库等多项辅助内容，读者朋友可以通过如下方式获取。
第1种方式：
（1）登录清华大学出版社的网站，在网页右上角的搜索文本框中输入本书书名（注意区分大小写和留出空格），或者输入本书关键字，或者输入本书ISBN号（注意去掉ISBN号间隔线“-”），单击“搜索”按钮。
（2）找到本书后单击超链接，在该书的网页下侧单击“网络资源”超链接，即可下载。
第2种方式：
访问本书的新浪微博：C语言图书，找到配套资源的链接地址进行下载。
配套资源目录如下图所示。
本书非常适合以下人员阅读。
? 从事编程行业的开发人员
? 有一定语言基础，想进一步提高技能的人员
? 大中专院校的老师和学生
? 即将走上工作岗位的大学毕业生
? 相关培训机构的老师和学员
? 编程爱好者第1篇　算法基础篇
第1章　程序之魂——算法
（ 自学视频、源程序：
配套资源\mr\01\） 2
1.1　魂之说 3
1.2　算法的特性 4
1.3　算法的表示方式 5
1.3.1　用自然语言描述算法 5
1.3.2　用流程图描述算法 5
1.3.3　用N-S图描述算法 8
1.3.4　用计算机语言描述算法 9
1.4　算法性能分析与度量 10
1.4.1　算法的性能指标 10
1.4.2　算法效率的度量 10
1.4.3　算法的时间复杂度 11
1.4.4　算法的空间复杂度 12
1.5　学习算法的原因 12
第2章　数据结构基础
（ 自学视频、源程序：
配套资源\mr\02\） 13
2.1　数据结构概述 14
2.1.1　数据结构的发展 14
2.1.2　数据结构的研究对象 14
2.1.3　数据结构与算法的关系 16
2.2　数据结构的基本概念 16
2.3　C语言常见数据结构 18
2.3.1　数组 18
2.3.2　结构体 20
2.3.3　链表 21
2.3.4　栈 23
2.3.5　队列 24
第3章　查找与排序算法
（ 自学视频、源程序：
配套资源\mr\03\） 26
3.1　查找算法 27
3.1.1　顺序查找 27
3.1.2　折半查找 29
3.1.3　分块查找 31
3.1.4　哈希查找 33
3.2　排序算法 38
3.2.1　选择排序 38
3.2.2　冒泡排序 40
3.2.3　直接插入排序 43
3.2.4　归并排序 45
3.2.5　希尔排序 48
3.2.6　快速排序 49
3.2.7　各种排序算法的比较 52
第4章　基本算法思想
（ 自学视频、源程序：
配套资源\mr\04\） 54
4.1　递归的概念和分治法 55
4.1.1　递归的概念 55
4.1.2　递归的应用——汉诺塔 55
4.1.3　分治法的基本思想 56
4.1.4　分治法的应用——棋盘覆盖
4.2　动态规划法 59
4.2.1　动态规划法的基本思想 59
4.2.2　动态规划的应用——最大
4.3　贪心算法 61
4.3.1　贪心算法的基本概念 61
4.3.2　贪心算法的应用——哈夫
4.4　回溯法 67
4.4.1　回溯法的基本思想 67
4.4.2　回溯法的应用——连续
邮资问题 68
4.5　分支限界法 70
4.5.1　分支限界法的基本思想 71
4.5.2　分支限界法的应用——旅行
售货员问题 71
第2篇　常用算法篇
第5章　数学算法
（ 自学视频、源程序：
配套资源\mr\05\） 76
5.1　随机数求π 77
5.2　正态分布的成绩 82
5.3　绘制最小圆 86
5.4　满意的一元二次方程解 93
5.5　计算定积分 101
5.6　分解质因数 103
5.7　最大公约数和最小公倍数 106
5.8　数字的全排列 109
5.9　递推化梯形法求解定积分 111
5.10　迭代法开平方运算 115
5.11　牛顿切线法解方程 117
5.12　改进欧拉方法求解微分方程 119
5.13　迭代法求解线性方程组 123
5.14　计算贷款利息 127
5.15　分数计算器 129
第6章　矩阵与数组问题
（ 自学视频、源程序：
配套资源\mr\06\） 132
6.1　“脱壳”组数 133
6.2　寻找矩阵中的“鞍点” 135
6.3　魔幻方阵 137
6.4　矩阵的转置运算 139
6.5　勾股数组 141
6.6　百灯判熄 143
6.7　巧排螺旋数阵 144
6.8　猜数四问 146
第7章　经典算法
（ 自学视频、源程序：
配套资源\mr\07\） 149
7.1　约瑟夫环 150
7.2　八皇后问题 152
7.3　0-1背包问题 156
7.4　斐波那契数列 159
7.5　寻找水仙花数 161
7.6　爱因斯坦阶梯问题 162
7.7　进制转换算法 163
7.8　哥德巴赫猜想 165
7.9　验证四方定理 167
7.10　尼科彻斯定理 168
7.11　角谷猜想 170
7.12　prim算法求最小生成树 171
7.13　迪杰斯特拉算法 174
第3篇　趣味算法篇
第8章　数学趣题
（ 自学视频、源程序：
配套资源\mr\08\） 178
8.1　警察抓犯人 179
8.2　舍罕王的失算 181
8.3　百钱买百鸡问题 183
8.4　三色球问题 185
8.5　填数字游戏 187
8.6　渔夫捕鱼问题 190
8.7　移数字游戏 191
8.8　数字翻译器 194
8.9　猴子吃桃问题 198
8.10　马克思手稿中的数学题 199
8.11　判断回文式素数 200
8.12　完全数 204
8.13　自守数 206
8.14　一数三平方数 207
8.15　古稀数 209
8.16　亲和数 213
8.17　对调数 215
第9章　逻辑推理题
（ 自学视频、源程序：
配套资源\mr\09\） 218
9.1　魔术师的秘密 219
9.2　婚礼上的谎言 220
9.3　谁讲了真话 222
9.4　白纸与黑纸 223
9.5　判断坏球 224
9.6　打渔晒网问题 229
9.7　水池注水问题 231
9.8　寻找假币 232
9.9　常胜将军 234
9.10　巧算国王分财物 236
9.11　商人渡河问题 237
9.12　马踏棋盘 243
9.13　猜杏核 246
第4篇　算法竞技篇
第10章　计算机等级考试算法实例
（ 自学视频、源程序：
配套资源\mr\10\） 250
10.1　数组的下三角置数 251
10.2　查找单链表的结点 252
10.3　二维数组的元素排序 254
10.4　寻找二维数组的最大值 256
第11章　程序员考试算法实例
（ 自学视频、源程序：
配套资源\mr\11\） 258
11.1　电话计费算法 259
11.2　处理链表的重复元素 261
11.3　剧场方形空位 263
11.4　数组的数值操作 265
11.5　三位数生成回文数 267
第12章　信息学奥赛算法实例
（ 自学视频、源程序：
配套资源\mr\12\） 269
12.1　我知你心 270
12.2　格雷码 272
12.3　狡猾的狐狸遇上聪明的兔子 275
12.4　6174问题 276
12.5　韩信点兵 279
12.6　杨辉三角 281
12.7　开关灯问题 284
12.8　蛇形方阵 286
新手上路我有疑问投诉建议参考资料 查看}