Какие есть способы отыскать макс. элемент в массиве?

← →
Kolan © (2007-06-02 11:00) [0]

1. Простой перебор.
2.
3.

Надо еще два. Поскажите?

← →
Anatoly Podgoretsky © (2007-06-02 11:03) [1]

2. Обращение к последнему элементу массива
3. Сортировка, потом пункт 2
4. метод случайных чисел, пока не попадешь

← →
Kolan © (2007-06-02 11:07) [2]

> Обращение к последнему элементу массива

Это не понял.

Сортировка, потом пункт 2  ок.

> метод случайных чисел, пока не попадешь

Не не годится :)

А покруче методы есть? Математические&#133

← →
Sergey Masloff (2007-06-02 11:09) [3]

Обращение к последнему элементу отсортированного по возрастанию массива

← →
X9 © (2007-06-02 11:11) [4]

Двоичный поиск, следящий поиск.

← →
Kostafey © (2007-06-02 11:11) [5]

По большому счету для неиндексированого массива
кроме простого перебора вариантов нет.
Тут нужна сортировка (а вот уж для сортировки вариантов много).

← →
X9 © (2007-06-02 11:12) [6]

> [4] X9 © (02.06.07 11:11)

Просьба не читать, перепутал с поиском конкретного значения.

← →
Alx2 © (2007-06-02 11:14) [7]

В любом случае сведется к полному перебору элементов массива, если нет никаких предположений о порядке в нем.
Сначала сортировать, а потом искать - страшненько, но сбособ, конечно.

Как способ, например, и проводка ломанной через точки массива и определения точной верхней грани получившегося :))

← →
Sergey Masloff (2007-06-02 11:16) [8]

X9 © (02.06.07 11:12) [6]
>Просьба не читать, перепутал с поиском конкретного значения.
а я только хотел.... ;-)

← →
Sergey Masloff (2007-06-02 11:18) [9]

Alx2 © (02.06.07 11:14) [7]
>Сначала сортировать, а потом искать - страшненько, но сбособ, конечно.
Кнут в этом страшного ничего не видел. Конечно куда ему до Alx2 но все таки наверное не так все страшно

← →
X9 © (2007-06-02 11:20) [10]

> [8] Sergey Masloff (02.06.07 11:16)
> а я только хотел.... ;-)

В смысле "просьба всерьёз не воспринимать" :)

← →
Alx2 © (2007-06-02 11:21) [11]

>Sergey Masloff (02.06.07 11:18)

Но ведь довольно просто сравнить время на сортировку со временем на полный перебор и решить что лучше?
Если невозможна сортировка не более, чем за линейное время - то перебор лучше. Это же очевидно?

← →
Alx2 © (2007-06-02 11:23) [12]

>Sergey Masloff (02.06.07 11:18)

>Конечно куда ему до Alx2

И зачем так писать? Уколоть хочется?

← →
Sergey Masloff (2007-06-02 11:24) [13]

Alx2 © (02.06.07 11:23) [12]
А что сильно уколол? Если сильно извини. Но подколоть НЕМНОГО хотелось
;-)

← →
Kolan © (2007-06-02 11:25) [14]

А градиентные спуски всякие годятся? Я просто wiki читаю и не врубаюсь :(

← →
Kolan © (2007-06-02 11:25) [15]

Мне надо сравнить типа что лучьше&#133

← →
Alx2 © (2007-06-02 11:28) [16]

>Sergey Masloff (02.06.07 11:24)

Понятно.

Уколол немного, так как вроде бы ориентируюсь в том, что пишу.
Только вернемся к поиску. Как можно через сортировку найти максимум быстрее, чем полным перебором?

← →
@!!ex © (2007-06-02 11:28) [17]

> Kolan © (02.06.07 11:25)

В хаотичном массиве, если поиск нужен только один раз - только перебор. Все остальное медленнее.

← →
Sergey Masloff (2007-06-02 11:32) [18]

Alx2 © (02.06.07 11:28) [16]
Нет я не говорю что быстрее. Просто способ вполне нормальный, классический можно сказать. А ты его так жестко сразу обозвал.

>Sergey Masloff (02.06.07 11:32) [18]

Ну вот. Жестокости не хотел, честное слово. :)

Да, это способ, конечно. Но часто тормозной.

> Все остальное медленнее.

Пох. Мне надо сравнить.

> X9 (02.06.2007 11:12:06) [6]

Ну почему и двоичный поиск даст тот же результат, как и обращение к последнему элементу массиву, правда не так оптимально, как через случайные числа, слишком быстро.

> Kolan (02.06.2007 11:25:15) [15]

Такой постановки вопроса не было, но сразу возникает сопутствующий вопрос, а по какому критерию. Критерий надо вынести в студию.

> Критерий надо вынести в студию.

По скорости. Те я на одинаковых данных буду считать TickCount.

может в этом смысле надо:
простая итерация, рекурсивная версия и сортировочная:)

> Kolan © (02.06.07 11:00)

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

> Разговор может быть о том, лишь как организовать этот перебор.

Так, понял.

А если я предпологать что в массиве не сл. числа, то тут уже появляются варианты, так?.
В массиве нечто похожее на нормальное распределения сл. чисел, те что-то вроде этого:
_____ / \ / \ ---/ \-----

Какие есть способы отыскать макс. элемент в массиве? Найти похожие ветки