Claire's Blog

甚麼是Prefix Sums（前綴和） 當需要快速查詢數組中某一區間的元素和時，Prefix Sums可以幫助我們在O(1)的時間複雜度內進行查詢。 具體做法是先對數組進行預處理，計算出從第一個元素到當前位置的所有元素的和，然後通過兩個元素的前綴和之差來計算出任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。 Prefix Sums通常用於需要頻繁查詢數組中某一區間的元素和的情況，例如在數學、統計學、計算機科學和機器學習等領域中。Prefix Sums的計算可以在預處理的階段中完成，因此可以在之後的查詢中以O(1)的時間複雜度快速地回答各種區間求和問題。 例如，在計算機科學中，Prefix Sums通常用於解決數組中的區間查詢問題，例如求解區間最大子段和、區間平均值、區間中位數等。Prefix Sums還可以用於在數據壓縮、圖像處理和信號處理等領域中，進行離散化、濾波和卷積等操作。 計算出從第一個元素到當前位置的所有元素的和，是因為這樣可以在之後的區間求和操作中，通過兩個元素的前綴和之差來快速計算任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。這樣可以大大降低區間求和操作的時間複雜度，提高算法效率。 Prefix Sums使用時機 在許多需要進行區間求和操作的問題中，Prefix Sums都是一種常用的解決方案。因此，在識別哪些問題需要使用Prefix Sums時，可以考慮以下幾點： 綜合以上幾點，可以初步判斷哪些問題可能需要使用Prefix Sums。在實際應用中，還需要進一步評估和優化算法，以確保其效率和準確性。 使用Binary Indexed Tree來計算前綴和 BIT的基本思想是將原始數組轉換為一個二進制表示的數組，並在其中儲存一些特定位置的前綴和。BIT的建立和查詢操作都可以在O(n log n)的時間複雜度內完成，其中n是數組的長度。BIT的更新操作可以在O(log n)的時間複雜度內完成。 更多詳細介紹: https://yuihuang.com/binary-indexed-tree/ 範例題目 – PassingCars 題目連結 https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/ 我的第一次解法(javascript) 成績如下，雖然答案是正確的，但是效率不夠，為O(N**2)，只拿到70%的分數 改善方向…

概念介紹 Counting Elements是一種計算數組中元素出現次數的概念。它通常用於解決一些與計數有關的問題，例如找出數組中出現次數超過一定閾值的元素，計算數組中不同元素的個數等。 在Counting Elements中，我們可以使用一個額外的數組counts，將數組中每個元素出現的次數記錄下來。counts[i]表示數組中元素i出現的次數，如果數組中不存在元素i，則counts[i]=0。 具體來說，Counting Elements算法的步驟如下： Counting Elements算法的時間複雜度為O(n)，其中n是數組的長度。它可以在線性時間內計算數組中元素的出現次數，因此非常適用於需要頻繁計算元素次數的問題。另外，Counting Elements算法還可以與其他算法結合使用，例如快速排序和二分查找等，以進一步優化計算效率。 使用時機 在許多與計數有關的問題中，Counting Elements是一種常見的解決方案。因此，在考慮使用Counting Elements時，可以考慮以下幾點： 綜合以上幾點，可以初步判斷哪些問題可能需要使用Counting Elements。在實際應用中，還需要進一步評估和優化算法，以確保其效率和準確性。 練習題目1 題目連結: FrogRiverOne – VIEW 我的解法 測試通過，為100%! 練習題目2 題目連結: PermCheck – VIEW 我的作答 練習題目3- MaxCounters 題目連結: MaxCounters – VIEW 我的解法 結果正確，但時間超時，只得到66的分數，代表需要再修改做法 我檢查了一下寫法，發現arr.fill(max_value)這行雖然只有一行，但是會是O(N)的複雜度，會增加許多的時間複雜度，因此，我嘗試最後再一次性的更新這個值，並且在每一步做加總時，檢查這個值是否需要被更新，就可以避免每次當A[i]>N時都得增加一次O(N)的時間複雜度。 https://app.codility.com/demo/results/training556V6C-HBV/ 練習題目4- MissingInteger…

什麼是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/ 結果如下