降低嵌套循环算法的时间复杂度 [英] Reducing the time complexity of an algorithm with nested loops

问题描述

我有以下要重写的算法，因此它具有时间复杂度O(n).我是算法的新手，但据我了解，由于两个for循环均进行n次迭代，因此复杂度始终为O(n ² ).甚至有可能降低其复杂性吗?

I have the following algorithm which I want to rewrite so it has time complexity O(n). I am new to algorithms but from my understanding since the two for loops both do a multiple of n iterations, the complexity will always be O(n²). Is it even possible to reduce the complexity of this?

Algorithm example(ArrayA, ArrayB, n)                                           
Input: 2 arrays of integers, ArrayA and ArrayB, both length n          
Output: integer

value <- 0                                                    1 operation
for i <- 0 to n-1                                             n-1 operations
    for j <- 0 to n-1                                         (n-1)^2 operations
        value <- value + (ArrayA[i] * ArrayB[j])              3(n-1)^2 operations
return value                                                  1 operation

原始操作总数:n ² + 2n-1，使其时间复杂度为O(n ² ).

Total primitive operations: n² + 2n - 1, giving it a time complexity of O(n²).

推荐答案

通过应用一些代数:

这是一种算法，可以在O(n)时间内计算出相同的结果:

So here is an algorithm which computes the same result in O(n) time:

sum_A ← 0
for i ← 0 to n-1
    sum_A ← sum_A + ArrayA[i]

sum_B ← 0
for j ← 0 to n-1
    sum_B ← sum_B + ArrayB[j]

return sum_A * sum_B

通常来说，不能总是更改带有嵌套循环的算法来降低时间复杂度；但是在某些情况下，您可以做到这一点，前提是您可以识别出特定于计算的内容，这意味着可以用不同的方式来完成.

Generally speaking, an algorithm with nested loops cannot always be changed to reduce the time complexity; but in some cases you can do it, if you can identify something specific about the computation which means it can be done in a different way.

对于像这样的总和，有时可以通过写代数等效的东西来更有效地计算结果.因此，遇到此类问题时，请戴上数学家的帽子.

For sums like this, it's sometimes possible to compute the result more efficiently by writing something algebraically equivalent. So, put your mathematician's hat on when faced with such a problem.

这篇关于降低嵌套循环算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！