為使用者檢索餘額的 Big-O 複雜度是多少？

這是與以下內容相關的問答：如何計算錢包的餘額？.

基於此：

**[Q]**為使用者檢索餘額的 Big-O 複雜度是多少？

是O（n）嗎，所以基本上我必須遍歷所有utxoset內容以找到匹配的輸出，這些輸出對應於它具有私鑰的公鑰（“你的密鑰”）？或者當我只提供我的公鑰時，是否有任何雜湊機制可以返回所有輸出？

感謝您寶貴的時間和幫助。

這取決於您將 UTXO 集放入的資料結構。不同的實現以不同的方式做到這一點，沒有一種方法可以設置 UTXO。

例如，一種實現可能不維護 UTXO 集，而是遍歷整個區塊鏈。這將是 O(n)，其中 n 是區塊鏈中 TXO 的數量。

其他實現可能會將 UTXO 設置在列表中，因此找到平衡仍然是 O(n)，其中 n 是 UTXO 的數量，因為它必須遍歷列表。

一個實現還可以在 scriptPubKey 上創建一個鍵控映射。該值將是相應輸出的列表（即數量和位置）。然後找到地址的餘額將是 O(1+k)，其中 k 是該地址的 UTXO 數量。這明顯小於 O(n)，因為查找哪些 UTXO 是 O(1)，但是您仍然必須遍歷所有這些 UTXO。

所以這個的時間複雜度真的取決於實現，沒有一種方法可以讓所有軟體都使用。但在大多數實現中，它可能是 O(n)。

引用自：https://bitcoin.stackexchange.com/questions/67357