算法复杂度

      算法的复杂度是以什么来度量的？

      算法的复杂度是以时间复杂度和空间复杂度来计算的。

①算法的时间复杂度

      算法的时间复杂度是指执行算法所需要的计算工作量。简单地说，时间复杂度是以时间来衡量的。一般来说，如果算法运行的时间越长，时间复杂度也就越高。但是同一个算法，它的运行时间也受到硬件设备的限制，硬件设备越好，运行时间越短。所以在衡量时间复杂度的时候，我们根据算法的基本语句来求解。

      值得注意的是：算法程序执行的具体时间和算法的时间复杂度并不是一致的。算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与这些因素无关。

      算法的计算工作量是用算法所执行的基本运算次数来度量的。算法所执行的基本运算次数与问题的规模有关，而算法所执行的基本运算次数是问题规模（通常用整数n表示）的函数。所谓问题规模就是问题的计算量的大小。

      在具体分析一个算法的工作量时，在同一个问题规模下，算法所执行的基本运算次数还可能与特定的输入有关。即输入不同时，算法所执行的基本运算次数不同。

②算法的空间复杂度

      算法的空间复杂度是指执行这个算法所需要的内存空间。简单地说，空间复杂度是算法在运行时临时占用内存空间大小的量度。

      算法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。其中，额外空间包括算法程序执行过程中的工作单元，以及某种数据结构所需要的附加存储空间。

      如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。

      为了降低算法的空间复杂度，主要应减少输入所占的存储空间以及额外空间，通常采用压缩存储技术。

总结：

      采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构很重要。

这东西详细手打有点，去帮你找了个讲的比较详细的。

哪不懂可以追问

简单理解，时间复杂度就是执行语句被调用了多少次。

(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=0x<nx++)

{x=x+1}

x会从0到n-1循环，执行的语句就是将当前x值加入新的x中，总共调用n次；那么O(n)=n

(4）用2个嵌套FOR循环调用

for(x=0x<nx++)

{

for(y=1y<=ny++)

{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=0i<ni++)

i值变化是从0到n-1，共n次。

for(i=0i<=ni++)

i值变化是从0到n，共n+1次。

(3)注意for循环的调用顺序，从里面到外面进行的。

---