[Sarlug] Re: [Sarlug] [JT]Задача, помогите кому не лень

Masterhard masterhard на cdma-saratov.ru
Ср Сен 18 09:16:00 MSD 2002


А подсчитывается это так:

сложность сортировки - n log n
сложность прямого поиска - n
сложность бинарного поиска - log n

следовательно условие:

m * n < (n + m) log n => прямой поиск без сортировки
m * n > (n + m) log n => бинарный поиск с сортировкой


----- Original Message -----
From: "Богородский Роман [Novel]" <bogorodskiy на inbox.ru>
To: <sarlug на lug.ru>
Sent: Friday, September 13, 2002 8:57 PM
Subject: [Sarlug] [JT]Задача, помогите кому не лень


Имеется следующая задача:
"Дан массив из n элементов произвольной природы, требуется m раз выполнит
поиск в этом массиве. Определить, при каких соотношетниях n и m следует
использовать одну из двцх методик :
1. Прямой поиск
2. Бинарный поиск с упорядочиванием массива."
Вот такая задача. По-моему ответ если n/m>2  тогда 1, иначе 2. Может это и
неправильно, не знаю. В общем, как это точно подсчитать?




Best regards.

Богородский Роман [Novel]
bogorodskiy на inbox.ru
2002-09-13



_______________________________________________
Sarlug mailing list
Sarlug на lug.ru
http://lug.ru/mailman/listinfo/sarlug






Подробная информация о списке рассылки Sarlug