求算法复杂度详解

1. 求算法复杂度详解

T(n)表示的是时间复杂度 这个没问题吧？
时间复杂度 说的是时间增量与时间频度成正比  即当n趋近于个很大的数时 有T(n)=O(f(n))
求解时间复杂度的步骤大概是这样的
1.从一个算法中找出时间频度（即基本语句的执行次数）即T(n).这里你已经找出来了T(n)=n^2+3n+4与T(n)=4n^2+2n+1
2.找出T(n)的同数量级(这些数量级有1< log2底n <n <nlong2底n <n^2 <n^3< 2^n <n!) 你那两个时间频度的同数量级都是n^2 级取n的最高次项
3.f(n)=n^2  lim(T(n)/f(n))=c(时间增量与时间频度成正比 比值为某常数C）
4.T（n）=O(n^2)
解毕

2. 算法复杂度的复杂度分析

通常一个算法的复杂度是由其输入量决定的，随着输入的增加，不同算法的复杂度增长速度如右图所示：为了降低算法复杂度，应当同时考虑到输入量，设计较好的算法。

3. 算法本身的复杂度怎么估计？

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

4. 算法复杂度

       算法的复杂度是以什么来度量的？  
  
       算法的复杂度是以时间复杂度和空间复杂度来计算的。
  
 ①算法的时间复杂度
  
       算法的时间复杂度是指执行算法所需要的计算工作量。简单地说，时间复杂度是以时间来衡量的。一般来说，如果算法运行的时间越长，时间复杂度也就越高。但是同一个算法，它的运行时间也受到硬件设备的限制，硬件设备越好，运行时间越短。所以在衡量时间复杂度的时候，我们根据算法的基本语句来求解。
  
        值得注意的是：算法程序执行的具体时间和算法的时间复杂度并不是一致的。算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与这些因素无关。
  
       算法的计算工作量是用算法所执行的基本运算次数来度量的。算法所执行的基本运算次数与问题的规模有关，而算法所执行的基本运算次数是问题规模（通常用整数n表示）的函数。所谓问题规模就是问题的计算量的大小。
  
       在具体分析一个算法的工作量时，在同一个问题规模下，算法所执行的基本运算次数还可能与特定的输入有关。即输入不同时，算法所执行的基本运算次数不同。
  
 ②算法的空间复杂度
  
       算法的空间复杂度是指执行这个算法所需要的内存空间。简单地说，空间复杂度是算法在运行时临时占用内存空间大小的量度。
  
        算法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。其中，额外空间包括算法程序执行过程中的工作单元，以及某种数据结构所需要的附加存储空间。
  
       如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。
  
       为了降低算法的空间复杂度，主要应减少输入所占的存储空间以及额外空间，通常采用压缩存储技术。
  
 总结：
  
       采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构很重要。

5. 算法复杂度的计算

同一个问题可以用不同的算法解决，而一个算法的质量优劣将会影响到算法甚至程序的运行效率。一个算法的好坏主要从时间复杂度和空间复杂度来计算。
  
      时间复杂度 
  
     一个算法所耗费的时间实际上是不能算出来的，必须上机运行才能知道。但我们也不需要对每个算法都去进行测试，只需要知道哪个算法耗时多，哪个算法耗时少就可以了。一个算法花     费的时间与算法中语句执行的次数成正比，哪个算法中语句执行次数多，它花费时间就多。
  
     一个算法所耗费的时间=算法中每条语句的执行时间之和
  
     每条语句的执行时间=语句的执行次数(即频度)×语句执行一次所需时间
  
     一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的 渐进时间复杂度。
  
 所以我们可以得出的结论是：算法执行时间可以用执行次数表示。
  
      空间复杂度 
  
 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作：
  
  S(n)=O(f(n)) 
  
 算法执行期间所需要的存储空间包括三个部分：
  
  1.算法程序所占的空间； 
  
  2.输入的初始数据所占的存储空间； 
  
  3.算法执行过程中所需要的额外空间。 
  
 具体的例子可以参考 十分钟搞定时间复杂度 
  
 
  
  
 转自：https://github.com/cttin/cttin.github.io/issues/17

6. 算法复杂度

每个表达式的算法复杂度是以最高的复杂度为准，所以有：
O(f(n)=O(n^4)
O(g(n)=O(n^4)
O(h(n)=O(n^3.5)
据此可以知道选项(2)、(3)都是错的。

7. 算法复杂度的介绍

算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

8. 算法复杂度求解

算法复杂度的递推式一般不完整, 所以需要单调性的假设

第一个问题, 常数项记成C, 并引进两个递推式
U(n) = U(n*0.8) + C
L(n) = L(n/2) + C
T介于U和L之间, 很容易证明U(n)和L(n)都是Θ(logn)的

第二个问题, 换元n=2^(2^k)之后可得
T(n) = F(k) = F(k-1) + Θ(k)
所以
T(n) = F(k) = Θ(k+(k-1)+...+1) = Θ(k^2) = Θ[(loglogn)^2]