1 仅仅依赖于问题规模的时间复杂度
(1) 例1: 交换i和j的内容
t = i;
i = j;
j = t;
以上三条语句的频度均为1,该算法段的执行时间是一个与问题规模n无关的常数。
因此,算法的的时间复杂度为常数阶,记作T(n)=O(1)。
算法的时间复杂度是O(1)。
(2) 例2: 循环次数直接依赖规模n
x = 0; y = 0;
for(k = 1; k <= n; k++)
x++;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
y++;
一般情况下,对计数循环语句只需考虑循环体语句的执行次数,忽略该语句中步长加1、终值判别、控制转移等成分。
因此,以上算法段中频度最大的语句是"y++",其频度f(n) = n*n。
算法的时间复杂度是O(n*n)。
当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
(3) 例3: 循环次数间接依赖规模n
x = 1;
for(i = 1; i <= n; i++)
for(j = 1; j <= i; j++)
for(k = 1; k <= j; k++)
x++;
该算法段中频度最大的语句是"x++"; 内层循环的执行次数虽然与问题规模n没有直接关系,但是却与外层循环的变量
取值有关,而最外层循环的直接次数直接与n有关。因此可以从内层向外逐层计算语句"x++"的频度:
f(n) = $(i:1~n)$(j:1~i)$(k:1~j) = $(i:1~n)$(j:1~i)j = $(i:1~n)(i*(i+1)/2) = (n(n+1)(2n+1)/6 + n(n+1)/2)/2
算法的时间复杂度是O(n*n*n)。
2. 算法的时间复杂度还与输入实例的初始状态有关
例: 在数组a[0, n-1]中查找给定的值k
i = n - 1;
while(i > 0 && a[i] != k)
i--;
return a[i];
频度较高语句为"a[i] != k"。此算法的频度不仅与问题规模n有关,还与输入实例中的a的各元素取值及k值有关。
<1> 若a中没有与k相等的元素,则语句的f(n) = n, 这是最坏情况;
<2> 若a的最后一个元素等于k,则语句的f(n) = 1,这是最好情况。
在求成功查找的平均情况时,一般假设查找每个元素的概率都是相同的,
则平均时间复杂度为:(1+2+...+n)/2 = (n+1)/2 = O(n)
分享到:
相关推荐
Hanoi(汉诺)塔问题作为一个古典的数学问题,一直以来都是数据结构中递归算法的经典案例, 几乎没有介绍过其他的方法来解决此问题。文章分析讨论了一种非递归算法。
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include #...
主要介绍了C++基于递归和非递归算法求二叉树镜像的方法,针对二叉树遍历结合实例形式分析了递归与非递归算法的实现与使用技巧,需要的朋友可以参考下
为构建数据结构中递归算法的统一知识体系,分析了常见数据结构的递归本质及递归算 法的组成要素,提出了递归算法转非递归算法的一般原则,根据递归算法的分类设计转换模型,通 过实例分析其可行性。
主要介绍了Java基于栈方式解决汉诺塔问题的方法,结合实例形式分析了java栈方式采用递归与非递归算法解决汉诺塔问题的相关操作技巧,需要的朋友可以参考下
本文只是简单的介绍动态规划递归、非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大。 [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 ...
主要介绍了JavaScript实现多叉树的递归遍历和非递归遍历算法,结合实例形式详细分析了JavaScript多叉树针对json节点的递归与非递归遍历相关操作技巧,需要的朋友可以参考下
递归算法具有简单自然、结构清晰、易于设计、可读性强等优点,但执行效率不高。为了节省存储空间并提高执行效率,人们更希望...在分析了递归算法和非递归算法执行原理的基础上,通过实例介绍了几种常用的消除递归的方法。
本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同。分享给大家供大家参考,具体如下: /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下: ***/ ...
主要介绍了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作,结合实例形式分析了php采用非递归算法对二叉树进行先序、中序及后序遍历操作的原理与具体实现技巧,需要的朋友可以参考下
2.2.1非递归算法分析 2.2.2递归算法分析 2.2.3提高算法质量 第二篇基础篇 第3章算法基本工具和优化技巧3.1循环与递归 3.1.1循环设计要点 3.1.2递归设计要点 3.1.3循环与递归的比较 3.2算法与数据结构 3.2.1原始信息...
主要介绍了python二分法查找算法实现方法,结合实例形式分析了Python使用递归与非递归算法实现二分查找的相关操作技巧,需要的朋友可以参考下
本文以实例形式讲述了C语言实现二叉树的非递归遍历方法。是数据结构与算法设计中常用的技巧。分享给大家供大家参考。具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node> s...
也应该学学非递归算法实现二叉树遍历。二叉树的非递归算法需要用到辅助栈,算法着实巧妙,令人脑洞大开。 以下直入主题: 定义一颗二叉树,请看官自行想象其形状, class BinNode( ): def __init__( self, val ): ...
本文实例讲述了C++非递归建立二叉树的方法。分享给大家供大家参考。具体分析如下: 思路: 设置一个标记变量flag并初始化为1. flag = 1表示现在需要创建当前结点的左孩子,2表示需要创建右孩子,3则表示当前结点的...
汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵求逆的快速算法 快 速 排 序 马踏棋盘问题 冒 泡 法 排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有...
主要介绍了PHP二分查找算法,结合实例形式分析了php基于递归与非递归方法实现二分查找的具体操作技巧,需要的朋友可以参考下
good)——图 15. 利用深度或广度优先搜索求...20. 递归算法与非递归算法的比较与复杂度分析(实例说明,具体数据) 21. 一种查找算法的改进及性能分析(实例说明,具体数据) 22.哈希表在字符串操作中的应用(字符串
主要介绍了C++非递归队列实现二叉树的广度优先遍历,实例分析了遍历二叉树相关算法技巧,并附带了两个相关算法实例,需要的朋友可以参考下