ListBox.FindString 最坏情况下的运行时间是什么？ O(n)、O(n log n)、O(1)？
出于好奇，ListBox.FindString(string) 最坏情况下的运行时间是多少？ MSDN 没有在其 API 文档中说明这一点。
我强烈怀疑它是 O(n)，我有一个排序列表，O(log n) 或 O(1) 会很好，有没有办法更改 FindString 在运行时使用的排序算法？
Out of curiosity, what is ListBox.FindString(string)'s worst case runtime? MSDN does not state this in its API docs.
I have a strong suspicion it is O(n), I have a sorted list and O(log n) or O(1) would be nice, is there a way to change which sorting algorithm FindString uses at runtime?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果 ListBox 中有足够的字符串，以至于 FindString() 的工作方式很重要，那么您需要考虑另一种存储字符串的方法。
If you have enough strings in the ListBox such that the big O of how FindString() works matters, you need to look at another way of storing your strings.
不管在列表框中包含大量项目是否是一个好主意（这对用户来说可能很麻烦，具体取决于您的实现。），我会猜测 O(n)因为我相信它会进行不区分大小写的部分匹配。
Regardless of whether its a good idea to have a huge number of items in a listbox to the point where it would matter (It might be cumbersome for the user, depending on your implementation.), I'm going to guess O(n) since I believe it does a partial match that is case insensitive.
实际上，您可以看到该方法的作用，因为 Microsoft 通过“Microsoft 参考源代码”提供其 .net 基类源代码 (clicky) - 您可以在 VS 中单步执行 BCL 代码（许多 BCL 内容也可以通过 Rotor（.net 的开源实现）获得，但是 WinForms 代码不可用IIRC）。
检查代码（我不想将其粘贴到此处，以防它违反 MS 的许可证），很明显该方法是 O(n) 最坏情况。
基本上，该方法循环遍历列表中的每个项目，如果到达底部则返回到列表顶部（通过巧妙地使用永远可爱的 mod (%) 运算符和计数器）。 显然，在最坏的情况下（即搜索的项目不在列表中），它必须迭代列表中的每个成员。
Actually, you can see what the method does, as Microsoft make their .net base class source code available via 'Microsoft Reference Source Code' (clicky) - you can step into BCL code in VS (also much of the BCL stuff is available via Rotor, the open source implementation of .net, however WinForms code is not available IIRC).
Examining the code (which I don't want to paste here just in case it violates MS's license), it's clear the method is O(n) worst-case.
Basically the method loops through each item in the list, moving back to the top of the list if the bottom is reached (through a crafty use of the ever-lovely mod (%) operator and a counter). Obviously that is O(n) in the worst-case (i.e. the searched-for item is not in the list) where it would have to iterate over every member of the list.
这听起来像是从列表开头开始的线性搜索，但没有办法确定。
您无法更改 ListBox 使用的算法，但您可以扩展 ListBox 并让您的扩展类执行您希望的任何操作。 ：D
That smells like a linear search from the start of the list, but there's no way to know for sure.
You can't change what algorithm ListBox uses, but you can extend ListBox and have your extended class do whatever you wish. :D