Алгоритм поиска в массиве

[elpilasgsm]

Добрый день.
Возможно я конкретно туплю, но может ли мне кто-нибудь подсказать быстрый метод поиска максимума (минимума) в одномерном неотсортированном целочисленном массиве. Сортировать массив не имеется возможности. Временная сложность должна быть меньше линейной

[Vanta11a]

Заводишь переменную, пишешь в неё значение 1го элемента массива.
Гонишь цикл по массиву. Если значение элемента больше(меньше) значения переменной, записываешь его в переменную.

После прогонки массива выводишь полученную переменную.

[elpilasgsm]

Для моей задачи это долго )). Спасибо за ответ)

[Vanta11a]

быстрый метод поиска максимума (минимума) в одномерном неотсортированном целочисленном массиве

Терзают сомненья, что более быстрый вообще существует, ибо проверять в любом случае надо все элементы.

[elpilasgsm]

Ну да. Я вот думаю просто, если проверять параллельно с начала до середины и с конца до середины. А потом выбирать между двумя. будет ли быстрее?

[Vanta11a]

Сложность даже выше, проверяются n+1 элементов.

n/2 + n/2 + 1

[Mandrivnyk]

Сообщение от elpilasgsm

Ну да. Я вот думаю просто, если проверять параллельно с начала до середины и с конца до середины. А потом выбирать между двумя. будет ли быстрее?

думаю, вряд ли

[veniside]

> будет ли быстрее?

быстрее может быть, но общая "временная сложность" останется постоянной и будет продолжать линейно зависеть от размера массива )

[elpilasgsm]

В общем я решил практически проверить. "Мой метод" оказался порядка 25% - 40% быстрее. Да ВСА осталась та же.

вот код:

long Max2 (long *mas, long lenght)
{
	long max;
	long max1=mas[0];
	long max2=mas[lenght-1];

		for (long i=1; i < lenght/2; i++)
		{
			if (max1<mas[i])
			{
				max1=mas[i];
			}
			if (max2<mas[lenght-i-1])
			{
				max2=mas[lenght-i-1];
			}
		}
		if (max1>max2) {
			max=max1;
		}
		else max=max2;
	return max;
}

[elpilasgsm]

А какой функцией С++ можно проверить само время. Не GetTickCount (). Что нибудь более тонкое))