ListBox.FindString, какое время выполнения в худшем случае? O (n), O (n log n), O (1)?

Question

Из любопытства, какое время выполнения ListBox.FindString (string) наихудшее? MSDN не заявляет об этом в своих документах API.

У меня есть сильное подозрение, что это O (n), у меня есть отсортированный список, и было бы неплохо O (log n) или O (1), есть ли способ изменить какой алгоритм сортировки FindString использует во время выполнения?

Answer 1

На самом деле, вы можете увидеть, что делает метод, поскольку Microsoft делает свой исходный код базового класса .net доступным через «Справочный исходный код Microsoft» ( clicky ) - вы можете перейти в код BCL в VS (также большая часть материалов BCL доступна через Rotor, реализацию с открытым исходным кодом .net, однако код WinForms недоступен IIRC).

Изучая код (который я не хочу вставлять здесь на случай, если он нарушает лицензию MS), становится ясно, что метод O (n) наихудший случай.

По сути, метод перебирает каждый элемент в списке, возвращаясь к вершине списка, если достигнуто дно (благодаря хитрому использованию всегда приятного оператора mod (%) и счетчика). Очевидно, что это O (n) в худшем случае (т. Е. Искомого элемента нет в списке), где он должен был бы перебирать все элементы списка.

Answer 2

Независимо от того, будет ли хорошей идеей иметь огромное количество элементов в списке до точки, где это будет иметь значение (это может быть неудобно для пользователя, в зависимости от вашей реализации.), Я собираюсь угадать O (n) поскольку я считаю, что это частичное совпадение, которое не учитывает регистр.

Answer 3

Если у вас достаточно строк в ListBox, так что большое значение работы FindString () имеет значение, вам нужно взглянуть на другой способ хранения ваших строк.

Answer 4

"Находит первый элемент в ListBox который начинается с указанного строка. "

Это пахнет как линейный поиск с начала списка, но точно знать это невозможно.

Вы не можете изменить используемый алгоритм ListBox, но вы можете расширить ListBox и сделать так, чтобы ваш расширенный класс делал все, что вы пожелаете. : D