Отправлено µ 21 апреля 2004 г. 15:16 В ответ на: Да все там понятно. отправлено -=ВН=- 21 апреля 2004 г. 14:35

потому как сравнение

if(a > filter[j])

никогда не даст минимальный элемент. А в остальном понятно. Найти N/2+1 минимумов и последний будет медианой. Надо будет (N/2+1)*N проходов массива. Итого имеем квадратичную сложность. Количество сравнений для 5 точек 5+4+3 = 12. При сортировке вставками у меня получилось 10 сравнений и 4 проходов массива. После оптимизации удалось сократить до 8 сравнений. Выигрыш от сортировки очевиден.

Приведенный алгоритм Гошей, наверное, хорош для больших массивов.
Все понятно, спасибо.

• И ошибки нет, потому как — -=ВН=-   (21.04.2004 15:24, 686 байт)
  • м-да. туплю что-то. ладно, согласен. — µ   (21.04.2004 15:28, пустое)