資料結構與算法:時間複雜度

算法的時間複雜度:具體分為時間複雜度和空間複雜度

大O表示法

對于代碼

void foo(){
    for(int i =0;i<n;i++){//0.執行了n次
        System.out.println("Hello world");//1.執行了n次
    }
    System.out.println("function over");//2.執行了1次
}      

01處執行了n次,2處執行了1次.假設算法總執行時間為T(n),其中n為問題的規模,上述總執行時間為

T(n) = (2n+1)*c

是以可以表示為

f(n) = 2n+1

有了執行次數後, 用大 (英語：Big O notation)來表示算法的複雜度, 即:

T(n) = o(f(n))

即時間複雜度為

T(n) = o(2n+1)=0(n)

在表示時間複雜度的時候, 大并不是表示代碼真正的執行時間, 而是表示代碼執行時間随着資料規模增長的變化趨勢. 一般具有以下特點:

1.不保留系數

2.隻保留最高階的項(随着資料規模n的增長, 低階項對結果的影響越來越小, 可以省去. 常數可以看成0階)

可以把大O符号想象成一個過濾性的漏鬥，過濾那些系數以及低階的項。

比如: f(n)=n^2, +1+n 則時間複雜度記為: o(n^2)

時間複雜度又分: 最優時間複雜度, 平均時間複雜度, 最壞時間複雜度. 一般平均複雜度更有指導意義.

對于冒泡排序

def bubbleSort(arr: Array[Int]): Unit = {
    for (i <- 0 until arr.length - 1) { // 
        for (j <- 0 until arr.length - 1 - i)   // 
            if (arr(j) > arr(j + 1)) { 
                swap(arr, j, j + 1)
            }
        }

    }   
}      

最優(最初有序)情況: 每次都不需要交換, 則隻需次數

是以時間複雜度是: o(n^2)

最差(最初逆序)情況: 每次都需要交換, 則每次增加三次交換:

是以時間複雜度是: : o(n^2)

平均情況:: o(n^2)

.其他排序算法時間複雜度

算法比較