Какой самый эффективный способ найти элементы в несортированном списке?

Question

Учитывая несортированный список в массиве, обязательно ли потребуется хотя бы линейное время, чтобы найти число элементов меньше x?Если так, то почему?

Answer 1

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

Answer 2

Если вы разрешаете неограниченное количество процессоров, вы можете решить эту проблему практически за постоянное время, предполагая, что конкатенация результатов выполняется быстро: просто разбейте массив на куски фиксированного размера и обработайте каждый блок на отдельном процессоре.

Если мы говорим об одном процессоре, я бы сказал, что вам нужно линейное время:

• вам нужно проверить каждый элемент и, если он соответствует предикату, поместить его в результат.
• сортировка или подобное не поможет, потому что вам снова нужно проверять каждый элемент хотя бы один раз.

Answer 3

Да, вам нужно хотя бы линейное время.Невозможно узнать, является ли элемент меньше x, не проверив его, поэтому вы должны проверить каждый элемент один раз.

Если вы сначала отсортировали его, то вы можете остановиться, как только элемент станет большех.