在VBA中使用这两种循环方式的时间复杂度有什么区别？

Question

我有一个理论问题,如果你在这里建议我会很感激.

说,我们有这两段代码.第一:

For Each cell In rng1
    collectionOfValues.Add (cell.Value)
Next

For Each cell In rng2
   collectionOfAddresses.Add (cell.Address)
Next

For i = 1 To collectionOfAddresses.Count
   Range(collectionOfAddresses.Item(i)) = collectionOfValues.Item(i)
Next i

在这里,我们将一个范围的地址添加到某个集合,将另一个范围的值添加到第二个集合,然后使用这些值填充这些地址上的单元格.

这是第二个代码,它是相同的:

For i = 1 To rng1.Rows.Count
  For j = 1 To rng1.Columns.Count
       rng2.Cells(i, j) = rng1.Cells(i, j)
  Next j
Next i

所以,问题是 - 两种情况下执行的时间是什么时候？我的意思是,很明显第二种情况是O(n ^ 2)(为了使我们更容易假设范围是正方形).

第一个怎么样？For Each被认为是嵌套循环吗？

如果是这样,是否意味着第一个代码的时间是O(n ^ 2)+ O(n ^ 2)+ O(n ^ 2)= 3*O(n ^ 2),这与第二个代码时间？

一般来说,这两个代码是否与第一个代码在创建集合时需要额外内存的事实不同？

非常感谢提前.

Answer 1

实际上,你的第一个例子是O(n ^ 4)!

这可能听起来令人惊讶,但这是因为索引到VBA集合具有线性而非常量的复杂性.VBA Collection基本上具有列表的性能特征 - 通过索引获取元素N 需要与N成比例的时间.通过索引迭代整个事物需要与N ^ 2成比例的时间.(我切换你的情况,以区分N,数据结构中的元素数量,从你的n,一个方块单元格一侧的单元格数.所以这里N = n ^ 2.)

这就是为什么VBA具有For ...每个用于迭代集合的符号的原因之一.当你使用For ... Each时,VBA在幕后使用迭代器,因此遍历整个Collection是O(N)而不是O(N ^ 2).

因此,切换回你的n,你的前两个循环使用For ...每个在一个范围内有n ^ 2个单元格,因此它们都是O(n ^ 2).你的第三个循环是在具有n ^ 2个元素的Collection上使用For ... Next,因此它是O(n ^ 4).

我实际上不确定你的最后一个循环,因为我不确切知道Range的Cells属性是如何工作的 - 那里可能存在一些额外的隐藏复杂性.但我认为Cell将具有数组的性能特征,因此O(1)用于通过索引进行随机访问,这将使最后一个循环为O(n ^ 2).

这是Joel Spolsky所说的"Shlemiel the painter's algorithm"的一个很好的例子:

在那里必须有一个Shlemiel画家的算法.每当看起来它应该具有线性性能但它似乎具有n平方性能时,寻找隐藏的Shlemiels.它们经常被您的图书馆隐藏.

(在stackoverflow成立之前查看此文章:http://www.joelonsoftware.com/articles/fog0000000319.html)

有关VBA表现的更多信息可以在Doug Jenkins的网站上找到:

http://newtonexcelbach.wordpress.com/2010/03/07/the-speed-of-loops/

http://newtonexcelbach.wordpress.com/2010/01/15/good-practice-best-practice-or-just-practice/

(我还要说明,如果这是一个"真正的"程序,而不仅仅是学习练习,那么cyberkiwi所说的不会通过Ranges来复制单元格内容.)