Является ли Big-O этой программы O (N^2)?

Я читаю Cracking the Coding Interview (новый). Кажется, что программа работает правильно. Когда я проверяю это, кажется, что N^2/2 - ответ. Я не думаю, что я прав. Может ли кто-нибудь сказать мне, что такое Big-O и почему?Является ли Big-O этой программы O (N^2)?

class Program 
    { 
     static void Main(string[] args) 
     { 
      int userNumber = Convert.ToInt32(Console.ReadLine()); 
      int[] makeAnArray = new int[userNumber]; 
      for (var x = 0; x < userNumber; x++) 
      { 
       makeAnArray[x] = x; 
      } 
      DisplayIterations(makeAnArray); 
     } 
     static void DisplayIterations(int[] testA) 
     { 
      int totalIterations = 0; 
      for (var i = 0; i < testA.Length; i++) 
      { 
       totalIterations++; 
       Console.WriteLine("i is " + i); 
       for (var j = i + 1; j < testA.Length; j++) 
       { 
        totalIterations++; 
        Console.WriteLine("j is " + j); 
       } 
      } 
      Console.WriteLine("The amount of iterations: " + totalIterations); 
     } 
    }

В основном функция принимает в массиве, запускает for петли для длины массива и для цикла length-1. Я положил 10, я получил 55 назад.

источник

2017-01-26 Drwooi Poipoi

O (N^2) и O ((N^2)/2) - одно и то же. – user2357112

Если вы не уверены, что вы правы, проведите простой эксперимент. Начните графику количества операций, выполняемых для разных входных значений, выбрав несколько различных входных значений и посмотрите, как начнет выглядеть график. – Servy

Мне не имеет смысла «вычислять большой-O» функции, которая просто выводит данные. Вам нужно будет пройти через все точки данных, чтобы их можно было выводить ... какая цель это служит? Вы не можете сделать это намного быстрее. –

Фактическое число итераций, где n является размер массива, является:

n(n+1)/2

которая может быть расширена до

(n^2 + n)/2

Однако в примечаниях Big O вы являетесь общими заинтересованные в классе алгоритмов, поскольку размеры ввода становятся большими и могут игнорировать обе константы (например, 2 в приведенной выше формуле), а также переменные с меньшим показателем, чем наибольшие, поэтому вы можете игнорировать компонент n, потому что n^2 будет очень, очень быстро перевешивает неквадратичный компонент, поскольку размер n увеличивается. Следовательно, вы бы назвали алгоритм с фактическим числом операций (n^2 + n)/ 2 просто как O (n^2).

Для справки, здесь есть определение Big O нотации из Wikipedia:

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

Объяснение того, почему у вас есть п (п + 1)/2 операции:

Вы итерация над массивом следующим образом:

for (var i = 0; i < arr.Length; i++) 
{ 
    for (var j = i + 1; j < arr.Length; j++) 
    { 
    } 
}

Я собираюсь выведите несколько примеров со следующими обозначениями:

i0 means that your program printed out 'i is 0' 
j1 means that your program printed out 'j is 1'

Давайте рассмотрим, что ваша программа woul d печатать с длиной массива 1, где каждая строка представляет собой целую итерацию внешнего цикла, а также внутренний цикл:

i0

Теперь с длиной массива 3:

i0 j1 j2 
i1 j2 
i2

С длина массива 6:

i0 j1 j2 j3 j4 j5 
i1 j2 j3 j4 j5 
i2 j3 j4 j5 
i3 j4 j5 
i4 j5 
i5

То, что вы можете легко увидеть, нарисовав его таким образом, что мы печатаем из 6 + 5 + 4 + 3 + 2 + 1 заявление при n = 6. Обратите внимание, что это это ju с добавлением всех целых чисел от 1 до 6 или более в общем случае от 1 до n. Общеизвестная формула для суммы целых чисел от 1 до n (сюрприз!) (n^2 + n)/2.

Я набрал это немного поспешно, но надеюсь, вы увидите, как я к этому пришел. Это согласуется с вашей оценкой, что для ввода длины 10 у вас есть 55 итераций: (10^2 + 10)/2 = (110)/2 = 55.

источник

2017-01-26 22:35:31

Да, Big-O этой программы O (N^2).

В обозначениях Big-O используются только доминирующие факторы (например, коэффициенты игнорирования).

Итак, хотя вы точнее (фактический ответ n (n-1)/2), нотация игнорирует ваш коэффициент 1/2 & любых факторов, меньших n^2, что является доминирующим фактором.

Смотрите этот ответ: Why do we ignore co-efficients in Big O notation?

источник

2017-01-26 22:32:53

Является ли Big-O этой программы O (N^2)?

ответ

Смежные вопросы