如何做这个嵌套的for循环时间复杂度？
How to do this nested for loop time complexity?
我正在尝试计算这个时间复杂度：
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 涉及某种类型的求和，但我不知道如何设置它...
基本上我需要帮助来可视化它循环了多少次，以及如何设置总和。谢谢！ :)
假设 m = n/2。您会看到在内循环中，j 将遍历范围 m-1、m-2、m-3、... 1。将所有这些加起来将是 1+2+..+m-1 = (m- 1)*m/2 = O(m^2)
前提
为简单起见，我们称m = n / 2 - 1。外循环从 0 运行到 m。从 i + 1 到 m.
的内部循环
迭代计数
我们需要计算您标记为 O(1) 的内部语句的执行频率。也就是说，内部循环运行的总频率与外部循环执行的频率相同。那么让我们一起来看看吧。
外循环的第一次迭代生成内循环的 m - 1 次迭代。第二个生成 m - 1，然后 m - 2、m - 3、m - 4、...、2、1、0。
这意味着 O(1) 语句总共执行了：
(m - 1) + (m - 2) + (m - 3) + ... + 2 + 1 + 0
这是从 0 到 m - 1
的总和
sum_{i = 0}^{m - 1} i
可以简化为
(m^2 - m) / 2
替补回来
现在让我们代入m = n / 2 - 1，我们得到
((n / 2 - 1)^2 - (n / 2 - 1)) / 2
简化后就是
n^2/8 - 3n/4 + 1
大O
对于Big-O，我们观察到它小于
n^2 - 0 + n^2
= 2n^2
根据定义，O(n^2)。
如您所见，这个界限也很紧。所以我们也收到 Omega(n^2) 也得出结论 Theta(n^2).
我正在尝试计算这个时间复杂度：
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 涉及某种类型的求和，但我不知道如何设置它...
基本上我需要帮助来可视化它循环了多少次，以及如何设置总和。谢谢！ :)
假设 m = n/2。您会看到在内循环中，j 将遍历范围 m-1、m-2、m-3、... 1。将所有这些加起来将是 1+2+..+m-1 = (m- 1)*m/2 = O(m^2)
前提
为简单起见，我们称m = n / 2 - 1。外循环从 0 运行到 m。从 i + 1 到 m.
迭代计数
我们需要计算您标记为 O(1) 的内部语句的执行频率。也就是说，内部循环运行的总频率与外部循环执行的频率相同。那么让我们一起来看看吧。
外循环的第一次迭代生成内循环的 m - 1 次迭代。第二个生成 m - 1，然后 m - 2、m - 3、m - 4、...、2、1、0。
这意味着 O(1) 语句总共执行了：
(m - 1) + (m - 2) + (m - 3) + ... + 2 + 1 + 0
这是从 0 到 m - 1
sum_{i = 0}^{m - 1} i
可以简化为
(m^2 - m) / 2
替补回来
现在让我们代入m = n / 2 - 1，我们得到
((n / 2 - 1)^2 - (n / 2 - 1)) / 2
简化后就是
n^2/8 - 3n/4 + 1
大O
对于Big-O，我们观察到它小于
n^2 - 0 + n^2
= 2n^2
根据定义，O(n^2)。
如您所见，这个界限也很紧。所以我们也收到 Omega(n^2) 也得出结论 Theta(n^2).