Чтобы сделать троичный поиск, нужно не только деление на 3, но и умножение на 2 (нам же на три части нужно разбить массив). Это раз.
Потом, нужно будет сравнить искомый элемент с двумя другими, т.е. две операции чтения и две операции сравнения (вместо одной и одной) и мы получаем 1/3 вместо 1/2. Но за два чтения и два сравнения двоичный поиск даёт уже 1/4.
Когда троичный может дать выгоду? Когда уже первое сравнение точно нам показывает, где находится элемент, т.е. в 1/3 случаев.
За это количество операций массив делится на 3. Чтобы разделить массив на 3*3*3*3*3*3 -- примерно тысяча, чуть меньше -- нужно 6 циклов, т.е. 10 * (1ч + 1ср) операций.
За такое количество операций двоичным делением мы делим массив на 1024 -- примерно тысяча, чуть больше.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
Date: 2010-01-28 08:26 pm (UTC)Потом, нужно будет сравнить искомый элемент с двумя другими, т.е. две операции чтения и две операции сравнения (вместо одной и одной) и мы получаем 1/3 вместо 1/2. Но за два чтения и два сравнения двоичный поиск даёт уже 1/4.
Когда троичный может дать выгоду? Когда уже первое сравнение точно нам показывает, где находится элемент, т.е. в 1/3 случаев.
Прикинем среднее количество операций на цикл
1/3 * (1ч + 1ср) + 2/3 * (2ч + 2ср) = 5/3 (1ч + 1ср)
За это количество операций массив делится на 3. Чтобы разделить массив на 3*3*3*3*3*3 -- примерно тысяча, чуть меньше -- нужно 6 циклов, т.е. 10 * (1ч + 1ср) операций.
За такое количество операций двоичным делением мы делим массив на 1024 -- примерно тысяча, чуть больше.