在我還是學生的時候，我參加了一個重逢時代的采訪. 面試問題有了新的記憶任務調度算法，因此您可以完成計劃的任務. 你會怎么做？為了簡化問題，我們只需要考慮內存方案，而不是數據持久性.

數組方法

最簡單的方法是，我們可以將所有任務存儲在一個數組中，然后每單位時間遍歷整個數組，以查找是否有一個任務滿足當前時間，如果有，則從數組中取出并執行. 每單位時間查詢算法的復雜度為O（N）. 那么，如何執行一項新任務？我們只需將一個元素添加到數組中，算法時間復雜度為O（1）

優先隊列方法

要評估算法，我們必須同時考慮其查詢算法復雜度和插入算法復雜度. 在計劃任務方案中，很明顯，有許多查詢方案. 幾乎我們必須每單位時間輪詢一次，因此我們可以優化算法嗎？每次查詢時，只要查詢時間最接近當前時間，該時間就會早于當前時間，并且必須將其丟棄. 因此，這個問題等于我們查詢隊列中的最小時間. 我們不禁想到一個熟悉的數據結構，優先級隊列！活著的我們可以使用一個小的根堆來實現. 每次插入新的定時任務時，都會將任務插入優先級隊列. 每次插入時，都需要調整隊列，算法時間復雜度為O（logN）. 值得注意的是，在討論算法時間復雜度時，logN為Base2，即N為8，logN為3. 類似地，盡管我們可以找到O（1）時間最小的任務，在此元素之外，需要在內部調整優先級隊列，算法時間復雜度也為O（logN）.

時間輪方法

上面優先級隊列的算法，綜合算法時間復雜度為O（logN），已經非常有效，但是在我們的大型并發分布式系統中，這個速度仍然太慢. 我們有更有效的算法嗎？那就是時間輪算法. 時間輪是循環隊列，根據時間單位進行劃分. 我們假設1秒. 每個單元中都有一個鏈接列表，用于存儲定時任務.

您可能會問，循環隊列中的元素畢竟是優先級. 如果超過長度任務調度算法，該怎么辦？我們可以想到我們家的水表，它也有很多輪子，并且每個輪子的單位都不同！時間輪也是如此. 我們可以使用多級時間輪進行優化. 就像我們的時鐘或水表一樣，這一層走來走去，下一層走來走去.

那么，如何計算該算法的時間復雜度？插入時，我們從最低層搜索以找到哪一層，然后直接插入相應的比例. 如果我們的時輪有5層，那么我們最多可以搜索5次. 查詢時，我們每秒推動一次時間輪的滾動，并且每次我們直接進入團隊的第一個元素時，這等效于算法O（1）的時間復雜度. 轉彎時，再次向下推下一層的下一個單元. 這樣，我們的一個元素將從第5層逐漸插入到第1層，集成的一個元素最多將插入5次. 在評估算法時間復雜度時，我們通常會忽略常數和最終算法時間，復雜度為O（1）.

摘要

一個非常簡單的面試問題，有幾種不同的解決方案. 這就是算法和數據結構的魅力. 歡迎大家跟隨我，共同學習，共同進步. 所有人的支持是我繼續聊天的動力.

本文來自本站，轉載請注明本文網址：
http://www.pc-fly.com/a/jisuanjixue/article-257476-1.html