TUhjnbcbe - 2023/10/26 17:08:00
定义：在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。（百度百科）。一个例子：输入：整型数组a[0,n-1]。输出：按非降序排列的数组a[0,n-1]。代码：publicvoidselectSort(int[]a){intn=a.length;for(intk=0;kn-1;k++){intmin=k;for(inti=k+1;in;i++){if(aa[min]){min=i;}}if(k！=min){inttemp=a[k];a[k]=a[min];a[min]=temp;}}}1.通过分析上面的代码我们可以得出比较次数为：2.同时也可以看出数据元素交换的次数在0到n-1之间，而每次交换需要使用3条赋值语句，因此数据元素的赋值在0到3(n-1)之间。那么我们是否可以根据n来计算出它的运行时间了呢？答案是否定的，也没有必要！这是因为影响实际运行时间的因素不仅有算法本身，还有其他诸多因素。例如算法是在什么机器上运行的，不同的机器其运算速度是不一样的；除了硬件的影响，操作系统以及使用的高级语言、编译系统都会对算法的实际运行时间造成影响。因此在对算法的运行时间做出分析时我们应该避免这些因素的影响，为此我们可以假设一些基本操作都是可以在一个常数时间内完成的。例如逻辑运算、赋值运算等都是基本操作。这样算法执行基本操作的次数可以反映算法的运行时间，在后面提到算法的运行时间时都是指运行基本操作的次数。如果算法分别对个整数排序以及对10^9个整数排序，其实际运行时间的差异是非常大的。这里就涉及到一个规模的问题。为此在分析算法的运行时间时我们必须将问题的规模（通常用n来表示）也考虑进去。显然算法执行基本操作的次数是关于规模n的非负函数，我们把它记为T(n)。例如在上面算法中当n不断变大时，算法执行的所有赋值语句对整个运行时间的影响就越来越小。为此我们可以将这些不重要的部分忽略，转而讨论运行时间的增长率或增长的阶。一旦去掉表示算法运行时间中的低阶项和首项常数，就称我们是在度量算法的渐进时间复杂度（asymptotic