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

我有一个理论上的问题，如果你在这里给我build议，会很感激。

说，我们有这两个代码段。第一：

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

所以，问题是 – 两种情况下的执行时间是多less？我的意思是，很明显，第二种情况是O（n ^ 2）（为了方便我们假定范围是方形的）。

那第一个呢？是为每个考虑一个嵌套循环？

如果是的话，是不是表示第一个代码的时间是O（n ^ 2）+ O（n ^ 2）+ O（n ^ 2）= 3 * O（n ^ 2）第二个代码时间？

一般来说，这两个代码的区别在于，第一个代码在创build集合时需要额外的内存。

非常感谢。

其实，你的第一个例子是O（n ^ 4） ！

这可能听起来令人惊讶，但是这是因为索引到VBA集合具有线性，而不是恒定的复杂性 。 VBA集合本质上具有列表的性能特征 – 通过索引获取元素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个元素的For … Next，因此是O（n ^ 4）。

我实际上并不确定你最后一个循环，因为我不知道Range的Cells属性到底是如何工作的 – 这里可能会有一些额外的隐藏的复杂性。但是我认为Cells将具有数组的性能特征，所以O（1）用于索引的随机访问，并且会使得最后一个循环O（n ^ 2）。

这是乔尔·斯波尔斯基（Joel Spolsky）称之为“史莱米尔画家的algorithm”的一个很好的例子：

在那里必须有一个Shlemiel画家的algorithm。每当有东西看起来应该有线性performance，但似乎有n平方的performance，寻找隐藏的Shlemiels。他们经常被你的图书馆藏起来。

（从stackoverflowbuild立之前，请参阅这篇文章： http : //www.joelonsoftware.com/articles/fog0000000319.html ）

有关VBA性能的更多信息，请参阅Doug Jenkins的webstie：

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循环来复制单元格的内容，如果这是一个“真实”的程序，而不仅仅是一个学习练习。）

你是对的，第一个是3 x O（n ^ 2），但要记住O-notation不关心常量，所以就复杂性而言，它仍然是一个O(n^2) algorithm 。

第一个不被认为是一个嵌套的循环，即使它在第二个循环中工作的尺寸相同。这只是Excel中N项范围的直接迭代。是什么使得N ^ 2是你将N定义为边的长度，即行数/列数（正方形）的事实。

只是一个Excel的VBA说明，你不应该在单元中循环，也不应该存储地址。这两种方法都不是最佳的。但我认为他们有助于说明您的问题，以了解O符号。

 rng1.Copy rng2.Cells(1).PasteSpecial xlValues Application.CutCopyMode = False

请记住，不要将您的代码的复杂性与后台Excel函数的复杂性混为一谈。在这两种情况下，所做的所有工作量都是N ^ 2。然而，在你的第一个例子中 – 你的代码实际上只有3N（三个循环中的每一个都是N）。 Excel中的单个语句可以填充多个值这一事实不会改变您编写的代码的复杂性。 foreach循环与for循环相同，N本身就是复杂的。当你嵌套循环时，你只能得到N ^ 2。

要回答你的问题哪个更好 – 通常最好是在你可以的情况下使用内置函数。这个假设应该是内部的Excel比你自己写的更有效率。然而（知道MS） – 确保你总是检查假设，如果性能是一个优先事项。