勵志

勵志人生知識庫

時間複雜度怎麼算

計算算法的時間複雜度通常遵循以下步驟:

找出算法中的基本語句,即執行次數最多的語句,通常是最內層的循環體條件語句

計算基本語句的執行次數,考慮循環、遞歸等結構,使用等差數列、等比數列的求和公式等數學工具來分析執行次數與問題規模n的關係。

用大O記號(O(f(n))表示算法的時間性能,時間複雜度是算法執行時間隨問題規模增長的趨勢,關注的是執行次數與問題規模n的關係,通常忽略低階項和常數項。

例如,對於循環語句for (i = 0; i < n; i++) {/* some code */},每次循環體執行一次,總共執行n次,其時間複雜度爲O(n)。對於嵌套循環for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {/* some code */}},每個內部循環執行n次,外部循環同樣執行n次,總時間複雜度爲O(n^2)。