我有以下陣列，我只是想確保我在每個解決方案運行的時間復雜度方面是正確的
arr = [3,6,8,10,34]
# case one
result_one = [arr[-1], arr[-2], arr[-3]]
# result = [34, 10, 8]
# case two
result_two = arr[-3:]
# result = [8, 10, 34]
基于 時間復雜度case one為常數 O(1)result_two的事實，切片方法是線性的 O(n)，case_one運行起來會更快。這兩種演算法的假設和時間復雜度是否正確？
uj5u.com熱心網友回復：
Big-O 運行時是關于隨著增加而增長的行為n。在這種情況下，n可以將其視為arr提取的專案的長度或數量：
- 就提取的專案數量而言，如果數量是可變的（不僅僅是常數
3），則兩個解決方案都是O(n). 如果數字是常數，大O是沒有意義的；您正在做固定數量的作業，不會改變，因此增長甚至不適用。 - 就長度而言
arr，在常數元素提取計數為 的情況下3，兩種解都是O(1)；除了長度為 0-2 的瑣碎情況外arr，所有arr長度為 3 或更大的 s 都需要相同數量的作業來提取三個元素；將大小加倍arr保持作業不變。
不管你怎么看，對于任何帶有O(1)索引的序列型別，這兩種解決方案在定義上都是相同的 big-O。在底層，切片必須完成與顯式索引完全相同的作業，因此它們必須執行相同數量的作業。
在具有非O(1)專案查找的序列型別上（例如，鏈表等，具有O(n)查找），就提取的專案數量而言，切片將優于對 big-O 的重復索引（因為它只需要找到起點切片的一次，而不是n次，使它成為鏈表的大小和O(m n)要提取的專案數，這簡化了因為你不能提取比你擁有的更多的專案，而重復索引將是，支付成本時間），但對于簡單的類似陣列的資料結構mnO(m)O(m*n)O(m)nO(1)索引時，兩者將始終是 big-O 等價的，盡管切片可能會更快，因為它可以批量執行操作，而不會一遍又一遍地進出 Python 級代碼。對于短輸入，它們的行為也會有所不同；如果輸入的元素少于三個，則切片會靜默回傳短輸出，而索引將隨著IndexError.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482715.html
標籤：Python 数组 python-3.x 算法 数据结构