Определить сложность алгоритма

[serj-07]

Всем здравствуйте!!!
Помогите как определить временную и емкостную сложность алгоритма решая задачу при равномерном и логарифмическом весовых критериях или подскажите где найти подробную информацию по данной теме.
ЗАДАЧА:
В массиве n целых чисел найти все пары элементов, сумма которых четна и сформировать новый массив из этих сумм.

спасибо.

[Smitt&Wesson]

Сообщение от serj-07

Всем здравствуйте!!!
Помогите как определить временную и емкостную сложность алгоритма решая задачу при равномерном и логарифмическом весовых критериях или подскажите где найти подробную информацию по данной теме.
ЗАДАЧА:
В массиве n целых чисел найти все пары элементов, сумма которых четна и сформировать новый массив из этих сумм.

спасибо.

Не совсем понятно, что означает "временная и емкостная сложность алгоритма" и "равномерный и логарифмический весовой критерий".
Если я правильно понял, необходимо определить время выполнения задачи, и её объём.
Время выполнения зависит от степени вложенности циклов, количества обрабатываемых в них данных и времени выполнения операций.
Каждый вложенный цикл, это степень, в которую возводится число исходных данных.
Например, если цикл один, - это N^1, если два - N^2 и т.д.
Объём зависит от к-ва введённых, исходных данных.
Для твоей задачи можно использовать два цикла for. Соответственно N^2*(f)ti .
Где N - к-во обрабатываемых данных;
f - к-во машинных команд в циклах (сумма от 1 до m);
t - время выполнения одной машинной команды.

[Sparkman]

Сообщение от serj-07

Всем здравствуйте!!!
Помогите как определить временную и емкостную сложность алгоритма решая задачу при равномерном и логарифмическом весовых критериях или подскажите где найти подробную информацию по данной теме.
ЗАДАЧА:
В массиве n целых чисел найти все пары элементов, сумма которых четна и сформировать новый массив из этих сумм.

спасибо.

http://abc.vvsu.ru/Books/ebooks_iskt...%DB/ocenka.htm

[Utkin]

Эффективность программы (кода) является очень важной ее характеристикой. Пользователь всегда предпочитает более эффективное решение даже в тех случаях, когда эффективность не является решающим фактором.

Ну-ну, это где? Не читайте это, а то сформируется неверное представление о жизни . То-то я смотрю Виста просто предел эффективности.

[Sparkman]

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

Ну-ну, это где? Не читайте это, а то сформируется неверное представление о жизни . То-то я смотрю Виста просто предел эффективности.

ему (топикстартеру) это для занятий скорей всего нужно
я такое тоже проходил))) один раз пользовался, также только ради того, чтобы подготовиться к паре

[Smitt&Wesson]

Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью.
For i:=1 to N do
For j:=1 to N do
Begin
...
End;
Сложность этой программы О(N2).

Поправка О(N^2).

1) для сложных алгоритмов получение O-оценок, как правило, либо очень трудоемко, либо практически невозможно,
2) часто трудно определить сложность "в среднем",
3) O-оценки слишком грубые для отображения более тонких отличий алгоритмов,
4) O-анализ дает слишком мало информации (или вовсе ее не дает) для анализа поведения алгоритмов при обработке небольших объемов данных.

Вообще, оценка алгоритма вещь весьма неблагодарная.
Об эту тему не один программист себе лоб рассшиб.
Для выбора "лучшего" алгоритма, есть простой способ.
Пишеш их штуки три. Тестируеш. И выбираеш тот, который более всего отвечает поставленным критериям.
Примерно так.