|
时间复杂度是指算法的时间耗费,是用来度量算法效率的一个很好的工具,是用数学极限思想中的等价无穷大O(...)来表示的, 往往是算法中各种操作次数的总和,就拿冒泡排序来说,对于n元数组A的排序如下: int out,in; public void bubbleSort() { for(out=n-1;out>1;out--) { //外部循环,从后向前 for(in=0;in<out;in++) { //内部循环,从前向后. if(A[in]>A[in+1]){ int tmp=A[x];//交换元素 A[x]=A[y]; A[y]=tmp; } } } } 对于变量in和in+1,在第一趟排序时进行了n-1次比较操作,第二趟排序进行了n-2次排序.如此类推,最后一次进行了1次比较,那么 对于n个数据项,进行比较的次数和就是, 1+2+3+...+n-2+n-1=(n-1)*n/2 这样算法进行了n*n/2次比较(当n很大时,减1可忽略),因为只有A[in]>A[in+1]时,交换才执行,那么交换的次数永远少于 比较的次数,如果数据是随机的,那么可以认为只有一半的数据进行了交换,则交换的总次数是n*n/4; 比较和交换的次数都和n的平方成正比,而常数是不算在大O表示法中的,所以可以认为冒泡排序运行需要O(n*n)时间级别. 它的时间复杂度就是O(n*n); 其它算法可以,以此类推,希望能够 帮到你. |
收藏
淘帖
踩
