什麼是BigO
時間複雜度是指算法所需的運行時間與輸入數據規模之間的關係。在計算機科學中，我們使用 BigO 表示法來表示算法的時間複雜度。
BigO 表示法中的 O 代表 “on the order of”，即算法的運行時間隨著輸入規模的增長，按照某種數量級的速度增長。常見的時間複雜度從低到高分別是 O(1)、O(log n)、O(n)、O(n log n)、O(n^2)、O(2^n) 和 O(n!)。
在實際應用中，我們通常希望選擇時間複雜度盡可能低的算法。然而，不同的算法在不同的應用場景下可能表現不同，因此選擇合適的算法需要根據具體問題進行綜合考慮。
另外需要注意的是，時間複雜度只是對算法的一個粗略估計，實際運行時間還受到很多其他因素的影響，如輸入數據的特性、計算機硬件性能等。因此，在實際應用中需要進行充分的測試和優化，以獲得更準確的運行時間估計。
降低常數
在 BigO 表示法中，常數因子通常被省略，因為它們對算法的增長速度影響相對較小。在特定輸入下O(N)可能會比O(1)更小，一般來說，BIG O只是在描述增加的速率。
降低非優勢條件
在算法的時間複雜度分析中，我們通常會關注最壞情況下的時間複雜度，即算法在處理最壞情況下的輸入時所需的時間複雜度。但是，在實際應用中，算法所處理的輸入可能並不總是最壞情況，因此可能存在一些非優勢條件，即輸入規模較小、輸入具有特殊性質等情況。
刷題範例
題目連結: https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/
我的解答 – https://app.codility.com/demo/results/training5HCTQQ-UW6/
function solution(A) {
// Implement your solution here
var total_a = 0;
var total_b = A.reduce((partialSum, a) => partialSum + a, 0);
var min = Infinity;
for(var i=0;i<A.length-1;i++){
total_a = total_a+A[i];
total_b = total_b-A[i];
//console.log(total_a, total_b,Math.abs(total_a-total_b), i)
if(Math.abs(total_a-total_b) < min){
min = Math.abs(total_a-total_b)
}
}
return min
}
結果如下
