下载文档原格式
时间复杂度o（1）,o（n）,o（logn）,o（nlogn）1、时间复杂度o(1), o(n), o(logn), o(nlogn)。
算法时间复杂度有的时候说o(1), o(n), o(logn), o(nlogn)，这是算法的时空复杂度的表⽰。
不仅仅⽤于表⽰时间复杂度，也⽤于表⽰空间复杂度。
O后⾯的括号中有⼀个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。
其中的n代表输⼊数据的量。
⼤O描述的是算法的运⾏时间和输⼊数据之间的关系。
2、时间复杂度为O(1)。
是最低的时空复杂度了，也就是耗时/耗空间与输⼊数据⼤⼩⽆关，⽆论输⼊数据增⼤多少倍，耗时/耗空间都不变。
哈希算法就是典型的O(1)时间复杂度，⽆论数据规模多⼤，都可以在⼀次计算后找到⽬标（不考虑冲突的话）。
3、时间复杂度为O(n)。
就代表数据量增⼤⼏倍，耗时也增⼤⼏倍。
⽐如常见的遍历算法。
再⽐如时间复杂度O(n^2)，就代表数据量增⼤n倍时，耗时增⼤n的平⽅倍，这是⽐线性更⾼的时间复杂度。
⽐如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
4、时间复杂度为O(logn)。
当数据增⼤n倍时，耗时增⼤logn倍（这⾥的log是以2为底的，⽐如，当数据增⼤256倍时，耗时只增⼤8倍，是⽐线性还要低的时间复杂度）。
⼆分查找就是O(logn)的算法，每找⼀次排除⼀半的可能，256个数据中查找只要找8次就可以找到⽬标。
指数函数：⼀般地，y=a^x函数(a为常数且以a>0，a≠1)叫做指数函数。
y=a^x表⽰a的x次⽅。
对数函数：如果a^x =N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的对数，其中a叫做对数的底数，N叫做真数。
5、时间复杂度为O(nlogn)。
就是n乘以logn，当数据增⼤256倍时，耗时增⼤256*8=2048倍。
这个复杂度⾼于线性低于平⽅。
时间复杂度：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂度”。
渐近时间复杂度：当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂度”。
当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
但是我们总是考虑在最坏的情况下的时间复杂度。
以保证算法的运行时间不会比它更长。
常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn请判断下列关系是否成立：（1） f(n)=O(g(n))（2） g(n)=O(f(n))（3） h(n)=O(n^1.5)（4） h(n)=O(nlgn)这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。
"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
这么一来，就好计算了吧。
◆ (1)成立。
题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
算法基础--简介时间复杂度与空间复杂度 算法是为求解⼀个问题所需要遵循的、被清楚地指定的简单指令的集合。
对于⼀个问题，⼀旦给定某种算法并且确定其实正确的，那么重要的⼀步就是确定该算法将需要多少诸如时间或空间等资源量的问题，这就是时间复杂度和空间复杂度存在的意义。
常⽤时间复杂度和空间复杂度来衡量不同算法的优劣。
⼀、从数学的⾓度理解 O(n)、Ω(n)、o(n)和Θ(n) 通常，我们以函数所处理的数据量来表⽰算法的性能，也就是说，对于⼤⼩为 n 的数据，我们⽤函数 f(n) 来表⽰它的算法性能。
在很多情况下，我们可以完全确定 f 的具体值，但是这通常不是必要的，我们更关⼼的是当算法处理的数据量变得⽆穷⼤时，算法的性能将趋近于⼀个什么样的值，即⼀个算法的增长速率（运⾏时间、占⽤空间的增长率）。
要描述这种增长率，需要⽤到⼀系列新的定义，这些定义的⽬的是要在函数间建⽴⼀种相对的级别，反映出⼆者之间的相对增长率。
1.1 Θ记法： Θ记法给出了⼀个函数的渐进上界和渐进下界。
对于⼀个给定的函数 g(n)，⽤Θ(g(n)) 来表⽰以下函数的集合： Θ(g(n)) = { f(n)：存在正常量c1、c2、n0，使得对所有 n >= n0，有 0 <= c1g(n) <= f(n) <= c2g(n) } 即，f(n) = Θ(g(n)) 表⽰，对所有的 n>=n0，函数 f(n) 在⼀个常量因⼦内等于 g(n)，称 g(n) 是 f(n) 的⼀个渐进紧确界。
此外，有⼀个定理：对于任意两个函数 f(n) 和 g(n)，我们有 f(n) = Θ(g(n))，当且仅当 f(n) = O(g(n)) 且 f(n) = Ω(g(n))。
1.2 ⼤ O 记法： 对于⼀个给定函数 g(n)，⽤ O(g(n)) 来表⽰以下函数的集合： O(g(n)) = {f(n) ：存在正常量 c 和 n0，使得对所有 n>=n0，有 0 <= f(n) <= cg(n)} ⽤⼤ O 记法来给出函数的⼀个在常量因⼦内的渐进上界。
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)=Ｏ(f(n)),称Ｏ(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的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
2、空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。
记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。
讨论方法与时间复杂度类似，不再赘述。
（3）渐进时间复杂度评价算法时间性能主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。
详解时间复杂度计算公式(附例题细致讲解过程)摘要：一、时间复杂度概念介绍1.定义2.重要性二、常见时间复杂度分类1.O(1)2.O(log n)3.O(n)4.O(n^2)5.O(n^3)6.O(2^n)三、时间复杂度计算方法1.增长率和指数级别2.常数阶、对数阶、线性阶、平方阶和立方阶四、例题讲解1.求解斐波那契数列的时间复杂度2.求解排序算法的时间复杂度3.求解二分查找算法的时间复杂度五、时间复杂度优化方法1.优化算法策略2.数据结构选择六、总结与实践应用1.掌握时间复杂度概念2.熟练运用常见时间复杂度分类3.提高算法分析和优化能力正文：一、时间复杂度概念介绍1.定义时间复杂度是用来估计算法运行时间的一个指标，通常用大O符号（O）表示。
它描述了算法在最坏情况下的运行时间增长速度，是评价算法效率的重要标准。
2.重要性掌握时间复杂度概念有助于我们：（1）预测算法性能：通过比较不同算法的时间复杂度，预测算法在实际应用中的性能表现。
（2）优化算法：根据时间复杂度分析，找出算法中的瓶颈，有针对性地进行优化。
二、常见时间复杂度分类1.O(1)：常数阶，代表算法运行时间与输入规模无关，如访问数组元素、哈希表查找等。
2.O(log n)：对数阶，代表算法运行时间与输入规模的对数成正比，如二分查找、红黑树查找等。
3.O(n)：线性阶，代表算法运行时间与输入规模成正比，如遍历数组或列表、线性查找等。
4.O(n^2)：平方阶，代表算法运行时间与输入规模的平方成正比，如冒泡排序、插入排序等。
5.O(n^3)：立方阶，代表算法运行时间与输入规模的立方成正比，如选择排序、希尔排序等。
6.O(2^n)：指数阶，代表算法运行时间随输入规模呈指数级增长，如解决旅行商问题（TSP）等。
三、时间复杂度计算方法1.增长率和指数级别：通过观察算法运行时间与输入规模的关系，判断时间复杂度。
如增长率恒定为k，则时间复杂度为O(k)。
2.常数阶、对数阶、线性阶、平方阶和立方阶：根据算法运行时间与输入规模的具体关系，确定时间复杂度类别。
时间复杂度讲解时间复杂度，这听起来有点玄乎的东西，其实就像是你去一个地方所花费的时间预估。
你比如说，你要去隔壁邻居家借个东西，这事儿简单得很，你几步路就到了，那这个就像是时间复杂度里比较简单的情况，花费的时间很少。
咱们来打个比方，假如有一个算法就像你从家门口走到小区门口的商店买个口香糖。
这个路程短，事情简单，你很快就能完成，这就好比一种时间复杂度很低的算法。
你可能会想，这有啥难理解的？嘿，这还只是个开头呢。
再说说另一种情况，就像你要去一个很远的地方旅游。
你得先收拾行李，然后去车站，可能还得转车，再到目的地，这一系列的事情就复杂多了，花费的时间也长。
在算法里，有些操作就像这样复杂的旅行，要做很多步骤，这时候时间复杂度就比较高了。
你看啊，时间复杂度呢，它不是确切地说这个算法要花多少秒多少分钟，它更像是一种量级的估计。
比如说有个算法是要找一个数组里有没有某个特定的数字。
如果这个数组很小，就像你在一个小盒子里找一颗特定颜色的珠子，那很容易，一下子就找到了。
可要是这个数组超级大，就像你在一个堆满了各种各样东西的大仓库里找一个小小的零件，那可就麻烦了，可能要花费很长时间。
再讲个有趣的故事吧。
从前有个小木匠，他要做一把椅子。
如果他只做一把简单的椅子，那他只要找几块木板，钉一钉，很快就做好了，这就像简单的算法，时间复杂度低。
但要是他要做一套特别复杂的雕花椅子，那他得先挑选合适的木材，然后精心雕刻花纹，再组装，这期间花费的功夫可就多了，这就如同时间复杂度高的算法。
我们常常会遇到这样的算法，就像在图书馆找一本书。
如果图书馆的书是按照书名首字母排列的，你知道你要找的书叫啥名，那你可能很快就能找到，就像在有序的数组里查找一个元素，速度比较快。
可要是这些书是乱七八糟堆在那里的，你要找一本书就像大海捞针一样难，这就是不同的算法结构带来的不同时间复杂度。
有时候你会想，为啥要这么在意时间复杂度呢？嘿，这就好比你去赶火车，如果你的路线规划得好，就像算法的时间复杂度低，那你就能轻松赶上火车。
时间复杂度与空间复杂度的概念你有没有听过“时间就是金钱”这句话？嗯，虽然说得挺老套，但其实它背后有个很深的道理，尤其在程序设计这个领域里，“时间”真的能决定你是不是能在一场“比赛”里获胜。
所以啊，我们今天就聊聊“时间复杂度”和“空间复杂度”这两个名词，这两位看似高大上的家伙，实际上和我们日常生活有着千丝万缕的联系。
相信我，你听懂之后，下一次写代码时，心里绝对能比之前轻松一大截。
说到时间复杂度，你可以把它理解为做一件事情需要多长时间。
比如你去超市买菜，拿一个篮子装满了蔬菜水果，再拿两个袋子装米和油，走到结账台的时候，看到前面排着长长的队伍，那你排队的时间肯定是个变量——有人慢，有人快，队伍长短不一，时间也随之变化。
这就像是一个程序执行过程中，所花费的时间，不同情况下会有不同的表现。
时间复杂度就是用来表示在最坏情况下（也就是超长队伍的情况），程序执行所需的时间增长趋势。
简单说，时间复杂度就是告诉你，这个程序一跑起来，得花多少时间，能不能接受。
它就像是你超市购物的速度，可能慢，也可能快，看你怎么设计。
你想啊，有的算法一运行，像风一样，几秒钟就搞定；有的则可能像拖拉机一样，慢吞吞的走，甚至在你等得发霉时，才捞出个结果。
时间复杂度告诉你，这种“拖拉机”式的慢，背后是怎么形成的。
举个简单的例子，假设你正在写一个查找程序，要从1000个数据中找一个特定的数。
如果你一个一个去试，最坏情况下你可能得试完所有的1000个数据，这就是O(n)的时间复杂度，意味着你的程序执行时间和数据量成正比。
可是，如果你有一堆有序数据，用二分查找一拆二，最多只需要做log(n)次比较，你猜，执行速度简直飞起来，O(log n)那是飞一般的感觉！每次只选一半，剩下的就是取巧了嘛，聪明人的做法！说到这里，你可能会想，既然时间这么重要，那是不是就要尽量选择最短的路径呢？嗯，这可不一定。
你没听过“事半功倍”吗？空间复杂度就像你收拾房间时的存储空间。
时间复杂度和空间复杂度的概念分为时间复杂度和空间复杂度。
其作⽤：。
其作⽤：时间复杂度是度量算法执⾏的时间长短；⽽空间复杂度是度量算法所需存储空间的⼤⼩。
算法复杂度 分为时间复杂度和空间复杂度算法复杂度 时间复杂度1.时间频度 ⼀个算法执⾏所耗费的时间，从理论上是不能算出来的，必须上机运⾏测试才能知道。
但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。
并且⼀个算法花费的时间与算法中语句的执⾏次数成正⽐例，哪个算法中语句执⾏次数多，它花费时间就多。
⼀个算法中的语句执⾏次数称为语句频度或时间频度。
记为T(n)。
2.计算⽅法 1. ⼀般情况下，算法的基本操作重复执⾏的次数是模块n的某⼀个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n）） 分析：随着模块n的增⼤，算法执⾏的时间的增长率和f（n）的增长率成正⽐，所以f（n）越⼩，算法的时间复杂度越低，算法的效率越⾼。
2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执⾏次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n，nLog2n ，n的平⽅，n的三次⽅，2的n次⽅，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到⼀常数c，则时间复杂度 T（n）=O（f（n）） 例：算法：for（i=1;i<=n;++i） {for(j=1;j<=n;++j) { c[i][j]=0; //该步骤属于基本操作执⾏次数：n的平⽅次 for(k=1;k<=n;++k){c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作执⾏次数：n的三次⽅次} }}则有 T（n）= n的平⽅+n的三次⽅，根据上⾯括号⾥的同数量级，我们可以确定 n的三次⽅为T（n）的同数量级 则有f（n）= n的三次⽅，然后根据T（n）/f（n）求极限可得到常数c 则该算法的时间复杂度：T（n）=O（n的三次⽅）3.分类 按数量级递增排列，常见的时间复杂度有： 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平⽅阶O(n2)，⽴⽅阶O(n3),...， k次⽅阶O(nk), 指数阶O(2n) 。
如何理解时间复杂度和空间复杂度我们经常可以看到这样的描述：软件=数据结构+算法，可见算法基础对于⼀个程序员的重要性。
算法中，有两个基本概念：时间复杂度和空间复杂度。
时间复杂度：描述算法执⾏消耗的时间，时间越短，时间复杂度越低，算法越优秀；空间复杂度：描述算法执⾏所占⽤的内存空间，占⽤内存越少，空间复杂度越低，算法越优秀；因此，时间复杂度和空间复杂度是评价⼀个算法性能的主要指标。
那么如何计算⼀个算法的时间复杂度和空间复杂度呢？简单理解，计算时间复杂度就是评估⼀个算法完成后执⾏了多少⾏代码，也就是算法所消耗的时间，但是该如何⽤数学的⽅式其表⽰出来呢？假设现在有个⼀个算法需要执⾏n次运算，我们⽤T(n)表⽰，n即表⽰算法的规模（⽐如n=10时，循环输出10次Hello World；n=100时，循环输出100次Hello World）。
如果假设存在⼀个函数f(n)，表⽰随着n的变化，算法需要执⾏的次数，当T(n)=O(f(n))，那么O(f(n))即为算法的时间复杂度。
⽐如，⼀个普通的循环：public int calc(int n) {int total = 0;for (int i = 0; i < n; i++) {total += i;}return total;}当n越⼤，循环的次数越多，那么耗费的时间也就越⼤，也就是f(n)随着n线性增长。
那么该算法的执⾏时间T(n)=O(n)，即时间复杂度为O(n)。
再⽐如，⼀个双层循环：public int calc(int n) {int total = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {total += j;}}return total;}外层循环每循环⼀次，内层循环就循环了n次，那么代码总循环次数就是n*n。
那么该算法的执⾏时间T(n)=O(n^2) ，即时间复杂度为O(n^2)。
