Python 豆知識 — 你知道 len() 的時間複雜度是 O(1) 嗎?

上過程式設計課的人都會知道,如果想知道陣列長度,會需要走訪一遍陣列,計算共有幾個元素,這個做法就引起我一個疑問:

「Python 的 len() 函式是不是也走訪 list, string, dict 等才能得到長度?如果一直對同一個 object 呼叫 len() 函式不就浪費很多時間在走訪?」

後來查了才知道,原來 len() 函式的時間複雜度是 O(1), 也就是說不管你對同一個 object 呼叫幾次 len() 函式,它都不是透過走訪的方式告訴你長度,而是立即回答你長度多少。

它的魔法也很簡單,就是 string, dist, list 等物件都有 1 個 dunder method __len__, len() 其實是呼叫 __len__() 取得長度,換句話說,當你對 string, dist, list 等物件進行操作時,它們都有額外紀錄現在長度,例如:

>>> 'abc'.__len__()
3

如果你有客製化的 class 需要紀錄長度的話,不妨也實作 __len__ dunder method 吧,如此就能用 len() 函式取得長度囉:

>>> class A(object):
...     def __len__(self):
...         print('called __len__()')
...         return 0
...
>>> len(A())
called __len__()
0

以上!

References

TimeComplexity - Python Wiki

Facebook Threads X

對抗久坐職業傷害

研究指出每天增加 2 小時坐著的時間,會增加大腸癌、心臟疾病、肺癌的風險,也造成肩頸、腰背疼痛等常見問題。

然而對抗這些問題,卻只需要工作時定期休息跟伸展身體即可!

你想輕鬆改變現狀嗎?試試看我們的 PomodoRoll 番茄鐘吧! PomodoRoll 番茄鐘會根據你所設定的專注時間,定期建議你 1 項辦公族適用的伸展運動,幫助你打敗久坐所帶來的傷害!

贊助我們的創作

看完這篇文章了嗎? 休息一下,喝杯咖啡吧!

如果你覺得 MyApollo 有讓你獲得實用的資訊,希望能看到更多的技術分享,邀請你贊助我們一杯咖啡,讓我們有更多的動力與精力繼續提供高品質的文章,感謝你的支持!