需要查找序列的開銷

Question

想象一下，數據結構有n個操作序列。第i個操作如果i是2的確切冪，則花費2i，如果i是3的精確冪，則花費3i，並且對於所有其他操作，花費1i。 以n爲單位，n個這樣的操作的總成本是多少？

基本上，需要弄清楚1和n之間有多少個2和3的冪作爲n的函數。

Answer 1

這裏有兩個提示：

1. 的2的冪小於n是floor(log2(n))數。
2. 2的第一個k次冪的總和爲pow(2,k)-1。