T1 时间复杂度计算

int sum = 0;
for (int i =1; i<n; i*=2) { // O(log n)
    for (int j=0; j<i; j++) { // O(i)
        sum++;
    }
}

• 外层循环：$O(\log n)$
• 内层循环：$O(i)$
• 总时间复杂度：$O({\sum }_{i=1}^{\log n}{2}^i)=O(2^{\log n})=O(n)$