Как рассчитать сложность алгоритма?

Question

[kot-samolet]

Например, программа анализирует текст и извлекает из него 5 параметров, они складываются в массив. На следующем этапе идёт обработка списка таких массивов, и при обработке каждого требуется найти максимальный элемент, т.е. сначала пробежаться по массиву.

Допустим при создании массива из 5 элементов можно добавить if и добавлять значение в начало или конец массива, таким образом мы потратим немного времени тут, но в списке массивов они уже будет всегда отсортированы и максимальный элемент будет всегда первым элементом массива.

В данном случае можно ли математически рассчитать быстрее будет работать варивант с предварительно отсортированным массивом или не отсортированным и как это сделать? (примем что условия выполнения и данные абсолютно одинаковые)

Comments

[Алексей Струков]

Что имеете ввиду под максимальным элементом?

[Lynn «Кофеман»]

Добавляя только в начало или конец вы не можете гарантированно получить отсортированный массив.

Для массива из 5 элементов время поиска максимума можно считать незначительной константой.

Все оценки сложности имеют смысл для массивов с как минимум десятками, а то и сотнями элементов.

[kot-samolet]

Алексей Тен: В массиве будут сотни, тут просто пример

Добавляя только в начало или конец вы не можете гарантированно получить отсортированный массив

ок, я введу доп. элемент массива в котором максимум будет храниться отдельно

Хотелось бы всё же попытаться рассчитать

[kot-samolet]

Алексей Струков: тут будет в каждый элемент большого массива вложен маленький массив. В маленьком массиве представим себе значения 0,5,2,9,5 - вот 9 в конкретно этом массиве максимальный элемент (с макс. значением, я в вопросе неверно выразился)

[Lynn «Кофеман»]

kot-samolet:
Что тут считать? Сортировка имеет сложность O(n log n), запоминание и обновление максимума в процессе заполнения массива O(n), т.е. очевидно сложность меньше ценой большего потребления памяти.

Но, кстати, для нахождения максимума сортировка не нужна, сложность поиска максимума тоже O(n).

Answer 1

[res2001]

Допустим при создании массива из 5 элементов можно добавить if и добавлять значение в начало или конец массива

Ну одним IF тут не обойтись и не обязательно в начало или в конец добавлять, что варианта добавления между элементами вы не рассматриваете? Это когда в массиве только 1 элемент - будет 1 if. Но и с одним элементом есть проблема - в какое место в массиве вы его поместите изначально, ведь вы, в общем случае, не знаете какие дальше будут элементы.
Короче - оно примерно то на то и выйдет. Только если в варианте с последующей сортировкой, у вас есть алгоритм быстрой сортировке, то в варианте постоянно отсортированного массива - не известно на сколько хорошо вам удастся это реализовать.
И не ясно на каком ЯПе вы все это делаете.

Answer 2

[Андрюха]

Давайте попробуем, напишите псевдокод.