Худший случай работы Big O

Не могли бы вы объяснить, как я могу получить наихудший вариант Big O этого алгоритма. Я читал свой учебник, и я наткнулся на аналогичный алгоритм, похожий на этот, но до сих пор не понимаю логики.Худший случай работы Big O

int t=0; 
for(int x=0;x<num.length;x++){ 
    for(int y=0;y<num.length;y++){ 
     for(int p=0;p<num.length;p++){ 
      for(int w=0;w<num.length;w++){ 
       if(num[p][w]>num[x][y]) 
       { 
        t=num[x][y]; 
        num[x][y]=num[p][w]; 
        num[p][w]=t; 
       } 
      } 
     } 
    } 
}

источник

2014-09-28 Plrr

Логика довольно проста. Начнем с самого внутреннего цикла:

Этот цикл работает num.length раз. Его наихудшая сложность исполнения во время записи в формате O-O составляет O(n) при условии, что n = num.length.

for(int w=0;w<num.length;w++){ 
    ... 
}

Теперь, когда вы положили другой для цикла вокруг него длины p, он будет работать с выше для цикла p раз. Так что это O(pn). В вашем случае p = num.length = n так должно быть O(n*n) = O(n^2).

В вашем примере есть 4 вложенных цикла, поэтому ответ O(n^4).

Почему я игнорировал содержимое самой внутренней петли? Поскольку выполняется постоянное количество выполненных операций, пусть это число будет c. Асимптотический анализ, используемый в примечании большого О, гласит следующее: O(c) is equivalent to O(1). Это происходит от definition of big-O.

источник

2014-09-28 19:38:00 mostruash

Что делать, если у меня есть программа, а не какой-то конкретный алгоритм, который выполняет «что-то» в конкретном ». Предположим, у меня есть программа, которая управляет (выполняет) различные задачи, например, допустим, у меня есть программа, которая генерирует случайные числа в матрице (массив 2d), а затем сортирует их в порядке возрастания. Пользователю предлагается ввести любое число, которое заставит программу распечатать сообщение, определяющее, выбран ли номер в массиве или нет. Я должен оценивать каждое утверждение отдельно? – Plrr

Как различные алгоритмы с соответствующими знаками Big O доходят до завершения наихудшего времени работы (Big O), когда каждый алгоритм отличается. Например, когда программа имеет алгоритмы: O (n^2), O (1), O (n) .... Какая из них представляет всю программу? – Plrr

@Plrr Когда у вас есть несколько Big O. Затем это представление : наилучший сценарий, сценарий среднего размера и наихудший сценарий. В программировании мы стремимся к среднему сценарию. Однако, в зависимости от ввода данных, который у вас есть. Вы можете получить наилучший сценарий или даже самый худший сценарий. Во всем, что «случается больше всего», средний случай. Вы справляетесь с этим много. – Juniar

Если вы сравниваете элемент для; == или < или> против списка или массива размера n, тогда его худшим случаем является O (n).

Поэтому стоимость одного цикла: O (n), но у вас есть 4 для циклов с худшим случаем O (n).

Общая стоимость: n * n * n * n = Худший случай O (n^4).

источник

2014-09-28 20:20:12 Juniar

Худший случай работы Big O

ответ

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