Два вопроса о теории алгоритмов:

O(N)

не благодари

не трудоёмкость, а асимптотическую сложность по времени

поскольку для расчёта среднего значения тебе нужны все значения массива, тебе надо оценить сложность последовательного доступа к одному значению, домножить его на количество значений, и добавить сложность операции расчёта среднего

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

и

что, одновременно?

или оба пункта не знаешь как делать?

Как посчитать трудоемкость алгоритма

Анализ алгоритмов
Как найти временную сложность алгоритма

вычислить среднее арифметическое элементов одномерного массива.

А что, пройти по массиву сложив все элементы, и разделить на кол-во, уже не работает? :(

Да, одновременно. Пояснений найти не смог - инфы в методичке нима.

вычислить среднее арифметическое элементов одномерного массива.

Сложность O(N), можно пробовать распараллелить, т.е. разбить на части и считать сумму для них отдельно. Если N действительно большое, и распараллелить не получается, то есть более сложные структуры данных — дерево фенвика, оно же binary indexed tree.

Если для учебы, то берешь Кормен «Алгоритмы. Построение и анализ».

Если большая точность не нужна, то можно быстрее, чем O(N) — по методу Монте-Карло.

трудоемкость алгоритма

это как FPS человека - так же расчитывается :-)

Если большая точность не нужна, то можно быстрее, чем O(N) — по методу Монте-Карло.

Всё равно будет O(N).

Не угадал автора по заголовку. Скучаю по анонiмусу.

Не угадал автора по заголовку. Скучаю по анонiмусу.

да, его концентрированного безумия не хватает. школота ещё хуже :(

Разве не O(1)? Для массива из m <= 1000 элементов считаем среднее арифметическое -> O(m). Для массива больше 1000 элементов считаем среднее арифметияеское для 1000 рандомных элементов -> O(1).

С O(1) будет различаться точность оценки для разных объёмов данных, потому выборку делают как часть от N. В самом простом случае это k * N. Если считать правильно объём выборки, то может получиться более мудрёная зависимость доли от N.

Скучаю по анонiмусу.

а у тебя крепкие нервы однако