Здравствуйте, Кодт, Вы писали:

К>И вот тут уже асимптотика становится гораздо симпатичнее. Потому что, чем дальше от левого края (а точнее, — чем дальше от нулевого значения), тем бодрее мы начнём скакать по массиву.
К>Вполне может быть, что получим субквадратичное время.

Гораздо симпатичнее — это сколько?
Кстати, что значит субквадратичное время? На википедии это есть, но очень непонятно написано.

К>Но тут вот ещё какой интересный момент.
К>Если содержимое массива — супервозрастающая последовательность, то по-любому отхватим самую первую ~ n*n*log(n). Это случай наихудший, но и наиредчайший.
К>Чтобы найти не верхнюю, а среднюю оценку, придётся теорверить со страшной силой.

А как так получилось, что у меня за квадратичное время O(N^2) решается при любом случае? То есть моё решение более эффективное, чем твоё? Или где-то ошибка?

Здравствуйте, Кодт, Вы писали:

К>И вот тут уже асимптотика становится гораздо симпатичнее. Потому что, чем дальше от левого края (а точнее, — чем дальше от нулевого значения), тем бодрее мы начнём скакать по массиву.
К>Вполне может быть, что получим субквадратичное время.

Гораздо симпатичнее — это сколько?
Кстати, что значит субквадратичное время? На википедии это есть, но очень непонятно написано.

К>Но тут вот ещё какой интересный момент.
К>Если содержимое массива — супервозрастающая последовательность, то по-любому отхватим самую первую ~ n*n*log(n). Это случай наихудший, но и наиредчайший.
К>Чтобы найти не верхнюю, а среднюю оценку, придётся теорверить со страшной силой.

А как так получилось, что у меня за квадратичное время O(N^2) решается при любом случае? То есть моё решение более эффективное, чем твоё? Или где-то ошибка?

UPD: а, прочитал твоё еще одно сообщение, у тебя тоже в результате квадратичная. Ок.