1

Как правильно посчитать сложность алгоритма? Смотрю все примеры, которые есть на stackoverflow и все равно никак не пойму.

Сам алгоритм С#:

   class Program
{
    static int sum(int mas_kol)
    {
        int sum_arr = 0;
        int[] mas = new int[mas_kol];
        Random rand = new Random();
        for (int i = 0; i < mas.Length; i++)
        {
            mas[i] = rand.Next(-100, 100);
            if ((mas[i] % 2 != 0) && (mas[i] < 0))
                sum_arr += mas[i];
        }
        return sum_arr;
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Введите количество элементов в массиве: ");
        int mas_kol = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine("Сумма нечетных и отрицательных элементов = " + sum(mas_kol));
    }
}

Как я правильно понял - получается линейная сложность? Но как к такому выводу придти правильно?

1
  • А вы не смотрите примеры, а почитайте лучше толковые книги. Итоговую сложность поняли правильно.
    – A K
    12 мар 2021 в 12:46

1 ответ 1

3

У вас в коде один цикл по всем элементам массива. Рекурсии нет, вложенных циклов нет, досрочного выхода из цикла тоже нет. Поэтому сложность O(n) - линейная.

6
  • 3
    И что важно: внутри цикла все функции выполняющиеся за константное время.
    – A K
    12 мар 2021 в 12:47
  • 1
    @AK Но даже если бы и не за константное. Если время исполнения каждой из функций внутри цикла никак не зависит от n, разве это как-то повлияет на оценку сложности алгоритма?
    – CrazyElf
    12 мар 2021 в 12:50
  • @CrazyElf Значит, все я правильно понял. Спасибо! Нам дали пример с квадратичной сложностью, получается, что мне просто ничего не нужно считать, а просто в качестве ответа указать O(n)? Спасибо за точные пояснения. S=a^n+b^n T(N) = N1^n+N2^n T(N) = O(N^2) - квадратичная сложность.
    – Artem L.
    12 мар 2021 в 13:08
  • @ArtemL. С формулами я вам не подскажу, у меня чисто инженерный анализ )
    – CrazyElf
    12 мар 2021 в 13:17
  • 1
    Если оно не будет зависеть от N, но будет пропорционально какому-то M - то да, повлияет, надо будет перемножать. Мы с вами просто оба посмотрели на функции и увидели, что там всё константно, не зависит от N и типа пренебрегли эффектом. Но а если бы в цикле стоял бы какой-то поиск строки длиной M - пришлось бы учесть.
    – A K
    12 мар 2021 в 14:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.