循环的大O分析
循环的大O分析
提问于 2015-08-25 18:54:40
我必须分析这个循环和其他循环，并使用Big-O表示法确定它的运行时间。
for ( int i = 0; i < n; i += 4 )
for ( int j = 0; j < n; j++ )
for ( int k = 1; k < j*j; k *= 2 )`这是我到目前为止所知道的：
for ( int i = 0; i < n; i += 4 ) = nfor ( int j = 0; j < n; j++ ) = nfor ( int k = 1; k < j*j; k *= 2 ) = log^2 n现在我要解决的问题是循环的最终运行时间。我最好的猜测是O(n^2)，但是我不确定这是否正确。有人能帮上忙吗？
编辑:关于哦-> O的事情我很抱歉。我的课本上用的是“大-哦”
回答 2
Stack Overflow用户
发布于 2015-08-25 19:14:31
对数来说，内循环是正弦时间，但是正弦时间，它实际上是对中间循环的每次迭代，它需要O((J))时间(做内循环)，所以我们需要求和：O(log(j)).
- For (
O(log_2(j^2))log_2(j^2)=2log(j))。
j=1 { log(j) |log，...，n-1 } log(1) + log(2) + ... + log(n-1) = log((n-1)!)
由于log((n-1)!)在O((n-1)log(n-1)) = O(nlogn)中，因此我们可以得出中间循环执行O(nlogn)操作的结论。
- 注意，中循环和内循环都独立于
i，所以要得到总的复杂度，我们可以将n/4(外循环的重复次数)乘以中循环的复杂度，得到：
O(n/4 * nlogn) = O(n^2logn)
因此，这段代码的总复杂度是O(n^2 * log(n))
Stack Overflow用户
发布于 2015-08-25 19:13:57
如果循环变量以常量递增/递减(在下面的示例中是c)，则循环的时间复杂度被视为O(n)：
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}
for (int i = n; i > 0; i -= c) {
// some O(1) expressions
}嵌套循环的时间复杂度等于执行最里面语句的次数。例如，以下示例循环的时间复杂度为O(n²)：
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}
for (int i = n; i > 0; i += c) {
for (int j = i+1; j <=n; j += c) {
// some O(1) expressions
}如果循环变量除以/乘以常量，则循环的时间复杂度被认为是O(logn)：
for (int i = 1; i <=n; i *= c) {
// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
}现在我们有：
for ( int i = 0; i < n; i += 4 ) <----- runs n times
for ( int j = 0; j < n; j++ ) <----- for every i again runs n times
for ( int k = 1; k < j*j; k *= 2 )` <--- now for every j it runs logarithmic times.所以复杂度是O( n²logm)，其中m是n²，可以简化为O(n²logn)，因为n²logm = n²logn² = n² * 2logn ~ n²logn。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32202157
复制相关文章
相似问题