2

出于好奇，ListBox.FindString(string) 的最坏情况运行时是什么？MSDN 在其 API 文档中没有说明这一点。

我强烈怀疑它是 O(n)，我有一个排序列表，并且 O(log n) 或 O(1) 会很好，有没有办法改变 FindString 在运行时使用的排序算法？

4

4 回答 4

1

不管在列表框中有大量项目到重要的程度是否是一个好主意（这对用户来说可能很麻烦，具体取决于您的实现。），我猜测 O(n)因为我相信它会进行不区分大小写的部分匹配。

于 2009-03-11T17:58:06.157 回答
1

实际上，您可以看到该方法的作用，因为 Microsoft 通过“Microsoft 参考源代码”（clicky）提供了他们的 .net 基类源代码 - 您可以在 VS 中单步执行 BCL 代码（也可以通过Rotor，.net 的开源实现，但是 WinForms 代码不可用 IIRC）。

检查代码（我不想在这里粘贴，以防它违反 MS 的许可证），很明显该方法是O(n)最坏情况。

基本上，该方法循环遍历列表中的每个项目，如果到达底部，则返回列表顶部（通过巧妙地使用永远可爱的 mod (%) 运算符和计数器）。显然，在最坏的情况下（即搜索的项目不在列表中）是 O(n)，它必须遍历列表的每个成员。

于 2009-03-11T18:07:24.120 回答
1

如果您在 ListBox 中有足够的字符串，那么 FindString() 的工作方式的大 O 很重要，您需要查看另一种存储字符串的方法。

于 2009-03-11T17:33:02.427 回答
0

"查找 ListBox 中以指定字符串开头的第一项。"

这听起来像是从列表开始的线性搜索，但没有办法确定。

您无法更改 ListBox 使用的算法，但您可以扩展 ListBox 并让您的扩展类做任何您想做的事情。:D

于 2009-03-11T17:56:28.093 回答