algorithm - 如何做这个嵌套的for循环时间复杂度？

Question

我正在尝试计算这个时间复杂度:

for(i=0; i<=(n/2)-1; i++){
    for (j=i+1; j<=(n/2)-1; j++){
        --some O(1) thing--                
    }   
} 

据我所知，外循环本身就是 O(n/2)。但是对于内循环，我也无法思考如何分解 O(1) 执行的次数。

如果内部一个盯着 j=0 我可以做 n/2(inner) * n/2(outer) = O(n^2) 时间复杂度对吗？然而，由于 j 取决于 i，我认为从 i+1 到 n/2 涉及某种类型的求和，但我不知道如何设置它......

基本上我需要帮助来可视化它循环了多少次，以及如何设置总和。谢谢你! :)

Answer 1

假设 m = n/2。您会看到在内循环中，j 将遍历范围 m-1、m-2、m-3、... 1。将所有这些加起来将是 1+2+..+m-1 = (m- 1)*m/2 = O(m^2)