1楼:匿名用户
算法的时间复杂度:
为了便于比较同一问题的不同算法,通常从算法中抽取一种或者多种有代表性的基本操作,再以这些基本操作重复执行的次数与问题规模的关系t(n) 作为算法的时间性量度。
如果t(n) 和 f(n) 是n 的函数,当n →∞ 时,有t(n) / f(n) → c (常数c ≠ 0),记作:t(n) = o(f(n)),称o(f(n)) 为算法的渐近时间复杂度,简称时间复杂度。
算法的空间复杂度:
一个算法实现所占存储空间大致包含三方面:
1. 指令、常数、变量所占用的存储空间;
2. 输入数据所占用的存储空间;
3. 算法执行时所需的辅助空间;
前两者是必须的,通常将算法执行时所需的辅助空间作为分析算法空间复杂度的依据:s(n) = o(f(n)),其中f(n)的规则与时间复杂度一致。
算法设计与分析 已知某个算法的时间复杂度t(n)=o(f(n)),f(n)是什么函数?t(n)和f(n)是什么关系?
2楼:匿名用户
时间复杂度
算法分析
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
1、时间复杂度
(1)时间频度
一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。记为t(n)。
(2)时间复杂度
在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度t(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用t(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,t(n)/f(n)的极限值为不等于零的常数,则称f(n)是t(n)的同数量级函数。记作t(n)=o(f(n)),称o(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为o(1),另外,在时间频度不相同时,时间复杂度有可能相同,如t(n)=n2+3n+4与t(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为o(n2)。
按数量级递增排列,常见的时间复杂度有:
常数阶o(1),对数阶o(log2n),线性阶o(n),
线性对数阶o(nlog2n),平方阶o(n2),立方阶o(n3),...,
k次方阶o(nk),指数阶o(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
时间复杂度 t(n)=o(f(n)),的 o什么意思
3楼:1么么么么么哒
o(n)这个大o表示的是最坏情况下的时间复杂度,就比如你举的例子,一共n^3次乘法和n^3次加法,那么加起来就是2×n^3。然后如果有一个表达式f(n),使得n趋于无穷大的时候,lim(2×n^3)/f(n)=常数c,那么就可以用大o表示。表示为o(f(n)),而且规定f(n)的表达式是不带常数的系数的,那么在这里f(n)=n^3。
一般用大o表示算法复杂度只需要取次数最高的项,而且去掉系数就ok了,不用每次都这么算的。三重循环而且每重循环都执行n次的话直接o(n^3)就好了。
数据结构中算法的时间和空间复杂度怎么计算
4楼:匿名用户
你好.t(n)=o( f (n) ) 表示时间问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同.称作 时间复杂度.如下:1. 2.
for (i=1;i<=n;++i) 3. for ( j=1; j<=n;++j ) for (k+1;j<=n;++k) 基本操作“x增1”的语句的频度分别为1.n和n的平方.则这三个程序段的时间复杂度分别 为.o(1).
o(n)..o(n平方).分别为常量阶.线性阶.和平方阶...算法可能呈现 的时间 复杂度还有对数阶o(long n) .指数阶o(2 n方)等 .空间复杂度: s(n)=o(f(n))其中n为问题的规模(或大小).一个上机执行的程序 除了需要存储空间来寄存本身所用指令.常数.变量和输入数据外.也要一些对数据进行操作 的工作单元和存储一些为实现计算所需信息的空间.若输入数据所占的空间只取决于问题本身,和算法无关,则只要分析除输入和程序之处的额处空间,否则应同时考虑输入本身所需空间...
有点抽象...因为本人也学不好.所以.只能回答这些..见谅..
5楼:匿名用户
排序算法 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 分类 在计算机科学所使用的排序算法通常被分类为: 计算的复杂度(最差、平均、和最好表现),依据串列(list)的大小(n)。
一般而言,好的表现是o。(n log n),且坏的行为是ω(n2)。对於一个排序理想的表现是o(n)。
仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要ω(n log n)。 记忆体使用量(以及其他电脑资源的使用) 稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。
也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录r和s,且在原本的串列中r出现在s之前,在排序过的串列中r也将会是在s之前。 一般的方法:插入、交换、选择、合并等等。
交换排序包含冒泡排序(bubble sort)和快速排序(quicksort)。选择排序包含shaker排序和堆排序(heapsort)。 当相等的元素是无法分辨的,比如像是整数,稳定度并不是一个问题。
然而,假设以下的数对将要以他们的第一个数字来排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在这个状况下,有可能产生两种不同的结果,一个是依照相等的键值维持相对的次序,而另外一个则没有: (3, 1) (3, 7) (4, 1) (5, 6) (维持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改变) 不稳定排序算法可能会在相等的键值中改变纪录的相对次序,但是稳定排序算法从来不会如此。
不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较,如此在其他方面相同键值的两个物件间之比较,就会被决定使用在原先资料次序中的条目,当作一个同分决赛。然而,要记住这种次序通常牵涉到额外的空间负担。
排列算法列表 在这个**中,n是要被排序的纪录数量以及k是不同键值的数量。 稳定的 冒泡排序(bubble sort) — o(n2) 鸡尾酒排序 (cocktail sort, 双向的冒泡排序) — o(n2) 插入排序 (insertion sort)— o(n2) 桶排序 (bucket sort)— o(n); 需要 o(k) 额外 记忆体 计数排序 (counting sort) — o(n+k); 需要 o(n+k) 额外 记忆体 归并排序 (merge sort)— o(n log n); 需要 o(n) 额外记忆体 原地归并排序 — o(n2) 二叉树排序 (binary tree sort) — o(n log n); 需要 o(n) 额外记忆体 鸽巢排序 (pigeonhole sort) — o(n+k); 需要 o(k) 额外记忆体 基数排序 (radix sort)— o(n·k); 需要 o(n) 额外记忆体 gnome sort — o(n2) library sort — o(n log n) with high probability, 需要 (1+ε)n 额外记忆体 不稳定 选择排序 (selection sort)— o(n2) 希尔排序 (shell sort)— o(n log n) 如果使用最佳的现在版本 ***b sort — o(n log n) 堆排序 (heapsort)— o(n log n) **oothsort — o(n log n) 快速排序 (quicksort)— o(n log n) 期望时间, o(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 introsort — o(n log n) patience sorting — o(n log n + k) 最外情况时间, 需要 额外的 o(n + k) 空间, 也需要找到最长的递增子序列(longest increasing subsequence) 不实用的排序算法 bogo排序 — o(n × n!) 期望时间, 无穷的最坏情况。
stupid sort — o(n3); 递回版本需要 o(n2) 额外记忆体 bead sort — o(n) or o(√n), 但需要特别的硬体 pancake sorting — o(n), 但需要特别的硬体 排序的算法 排序的算法有
什么是时间复杂度、空间复杂度?
6楼:帅气的小宇宙
1、时间复杂度是指执行算法所需要的计算工作量。
时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大o符号表述,不包括这个函数的低阶项和首项系数。
2、空间复杂度是指执行这个算法所需要的内存空间。
空间复杂度需要考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。
空间复杂度也就是对一个算法在运行过程中临时占用存储空间大小的量度,记做s(n)=o(f(n))。比如直接插入排序的时间复杂度是o(n^2),空间复杂度是o(1) 。
7楼:love生活
1、时间复杂度:是指一个算法中的语句执行次数。
算法分析的目的在于选择合适算法和改进算法。
2、空间复杂度:是对一个算法在运行过程中临时占用存储空间的度量。
一个算法在计算机存储器上所占用的存储空间包括存储算法本身所占用的空间,算数和输入输出所占用的存储空间以及临时占用存储空间三个部分。
扩展资料:
在一个算法中,时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;
反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。
另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
算法的时间复杂度和空间复杂度合称为算法的复杂度
时间复杂度O(N)是什么,时间复杂度O(n)什么意思
1楼 匿名用户 就是级别为n的时间复杂度。是时间复杂度的其中一种算法 时间复杂度o n 什么意思 2楼 飞侠 闪电 时间复杂度 算法分析 同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考...
如何对n个数进行排序,要求时间复杂度o,空间复杂度o
1楼 mean有方法的 o什么,要知道,排序理论最快时间复杂度只能是nlogn,不能再快,这是有证明的。想要提高速度用c 函数库的qsort 如何对n个数进行排序,要求时间复杂度o,空间复杂度o 2楼 钟萌纳 题目 如何对n个不重复出现的整数序列进行排序 已知这些数的范围为 0 65535 要求时间...
如何对n个数进行排序,要求时间复杂度O,空间复杂度O
1楼 钟萌纳 题目 如何对n个不重复出现的整数序列进行排序 已知这些数的范围为 0 65535 要求时间复杂度o n 空间复杂度o 1 分析 可以申请一个大小为65536的数组a 数组的x下标代表数字x a x 代表x 在整数序列中出现的次数 扫描一遍整数序列就可以完成对该整数序列的排序 时间复杂度...