OverRedMaple责编
Carol来源
CSDN博客封图
CSDN付费下载于东方IC如果你还在发愁究竟怎么计算时间复杂度和空间复杂度，那你是来对地方了！名词解释：在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。时间复杂度的表示方法其实就是算法（代码）的执行效率，算法代码的执行时间。我们来看下面一个简单的代码：intsumFunc(intn){intnum=0;//执行一次for(inti=1;i=n;++i){//执行n次num=num+i;//执行n次}returnnum;}假设，每行代码的执行时间为t，那么这块代码的时间就是(2n+2)*t由此得出：代码执行时间T(n)与代码的执行次数是成正比的！那么我们来看下一个例子：intsumFunc(intn){intnum=0;//执行一次for(inti=1;i=n;++i){//执行n次for(intj=1;j=n;++j){//执行n*n次num=num+i*j;//执行n*n次}}}同理，该代码执行时间为(2n*n+n+1)*t，没意见吧？继续往后看！注意：在数据结构/算法中，通常使用T(n)表示代码执行时间，n表示数据规模大小，f(n)表示代码执行次数综合，所以上面这个例子可以表示为f(n)=(2n*n+n+1)*t，其实就是一个求总和的式子，O(大写O)表示代码执行时间与f(n)成正比例。根据上面两个例子得出结论：代码的执行时间T(n)与每行代码的执行次数n成正比，人们把这个规律总结成这么一个公式：T(n)=O(f(n))所以呢，第一个例子中的T(n)=O(2n+1)，第二个例子中的T(n)=O(2n*n+n+1)，这就是时间复杂度表示法，也叫大O时间复杂度表示法。但是，大O时间复杂度并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。与泰勒公式相反的是，算了，扯哪去了…当n变得越来越大时，公式中的低阶，常量，系数三部分影响不了其增长趋势，所以可以直接忽略他们，只记录一个最大的量级就可以了，所以上述两个例子实际他们的时间复杂度应该记为：T(n)=O(n)，T(n)=O(n*n)我想你应该明白大致是怎么回事了，那么我们来看看如何去计算它？时间复杂度的分析与计算方法（1）循环次数最多原则我们上面说过了，当n变得越来越大时，公式中的低阶，常量，系数三部分影响不了其增长趋势，可以直接忽略他们，只记录一个最大的量级就可以了。因此我们在计算时间复杂度时，只需