通常都會說 Python 的 set 內部是用 hash table 來實作，所以是 O(1)，但為什麼這樣就是 O(1)？
當要判斷某個元素是否在 set 裡面時，它的 __hash__() 會被用來得到 hash 值，可以把這個 hash 值視為 set 底層實作的 array 的 index，Python 接著會用這個 hash 值去那個 array 的對應位置找，然後發現 array 沒有這個位置，或是找到對應 value，而這個過程跟 set 裡的元素個數無關，所以是 O(1)
而這邊說的 O(1) 是平均時間複雜度，最壞情況時間複雜度是 O(n)，
x 次u_paths(0, 0)，此時 u_paths(i + 1, j) 需要呼叫 m 次才會停，u_paths(i, j + 1) 需要呼叫 n 次才會停，所以總共呼叫 m + n 次才會停，此時遞迴深度 h = m + nO(x^h)如果去 google，大部分查到的都會說因為 Python 會把 key 經過 hash function 運算，得到一個 dict 真正內部在使用的 key，從而找到對應的 value。而一個好的 hash function 它的運算所需時間是不會隨著 n 增加而變大的，所以 dict 的 get item operation 時間複雜度為 O(1) 。
不過我的疑惑是，經過 hash function 運算得到 key 之後，由這個 key 去找到 value 的時間複雜度是 O(1) 嗎？除非這個也是 O(1) 才能說整個 get item operation 是 O(1) 。
Update your browser to view this website correctly. Update my browser now
