호기심에서 ListBox.FindString (string)의 최악의 런타임은 무엇입니까? MSDN은 API 문서에이 내용을 기술하지 않았습니다.ListBox.FindString 최악의 런타임은 무엇입니까? O (n), O (n log n), O (1)?
O (n), 정렬 된 목록이 있고 O (log n) 또는 O (1)이 좋을 것이라는 강한 의구심을 가지고 있습니다. FindString을 사용하여 런타임에 FindString을 사용하는 방식을 변경하는 방법이 있습니까?
ListBox에서 FindString()이 어떻게 작동하는지에 대한 충분한 정보가있는 경우 문자열을 저장하는 다른 방법을 살펴 봐야합니다.
"지정한 문자열로 시작하는 목록 상자 의 첫 번째 항목을 찾습니다."
목록 시작 부분부터 선형 검색처럼 냄새가 나지만 확실히 알 수는 없습니다.
ListBox에서 사용하는 알고리즘을 변경할 수는 없지만 ListBox를 확장하고 원하는대로 확장 클래스를 만들 수 있습니다. : D
목록 상자에 엄청난 수의 항목을 포함하는 것이 좋은지 여부에 관계없이 (구현에 따라 사용자에게는 성가신 수 있음) 관계없이 O (n)을 추측하려면 대소 문자를 구분하지 않는 부분 일치를 수행한다고 생각하기 때문에.
사실, 당신은 방법은 마이크로 소프트로 'Microsoft 참조 소스 코드'를 통해 사용할 수 그들의 .NET 기본 클래스의 소스 코드를 만들어, 무엇을 볼 수있다 (clicky) - 당신이 (VS에서 BCL 코드에 많은도 단계 수 BCL은 Rotor를 통해 사용할 수 있습니다. 그러나 WinForms 코드는 IIRC를 사용할 수 없습니다.
코드 (MS의 라이센스에 위배되는 경우를 대비하여 여기에 붙여 넣기를 원치 않음)를 검사하면이 방법이 확실하지 않습니다. O (n) 최악의 경우입니다.
기본적으로이 메서드는 목록의 각 항목을 반복하며 맨 아래에 도달하면 목록의 맨 위로 이동합니다 (항상 mod (%) 연산자와 계수기를 교묘하게 사용). 분명히 최악의 경우 (즉, 검색된 항목이 목록에 없음) O (n)이면 목록의 모든 구성원을 반복해야합니다.
그래, 질문에 대답하는 것은 어떨까요? – Alan
ListBox.FindSTring()의 런타임은 거의 무의미합니다. UI 텍스트 상자는 적은 수의 문자열을 포함하도록 설계되었으므로 선형 검색이 허용됩니다. 거의 모든 알고리즘은 작은 N에서 빠릅니다. N이 매우 큰 경우 ListBox를 데이터 저장소로 사용하면 안됩니다. – Michael
나는 그것을 위해 멋진 O (1) 조회를위한 HashTable에 모든 것을 저장하려고했으나 100,000 개 이상의 "단어"를 가지고 ListBox와 HashTable 모두 메모리에 보관해야한다. ( – Kai