Обозначение Big O - Сомнения в петле - PullRequest
Новая
       24

Обозначение Big O - Сомнения в петле

0 голосов
/ 04 июля 2018

Недавно я начал анализировать нотацию Big O и получил очень простую проблему. На самом деле, я немного растерялся, и если кто-то может рассказать мне об этом, будет здорово.

Просмотр псевдокода ниже: 

Boolean: ContainsDuplicates(Integer: array[])
    // Loop over all of the array's items except the last one.
    For i = 0 To <largest index> - 1
        // Loop over the items after item i.
        For j = i + 1 To <largest index> N
            // See if these two items are duplicates.
            If (array[i] == array[j]) Then Return True
        Next j
    Next i

    // If we get to this point, there are no duplicates.
    Return False
End ContainsDuplicates

Я бы хотел понять, какой Big O представляет цикл ниже, поскольку начальное значение от j - это i + 1:

для j = i + 1 до N

Спасибо

Ответы [ 2 ]

0 голосов
/ 04 июля 2018

Спасибо. Я читаю книгу, и есть два разных подхода. Первый, как описано ниже: 

Boolean: ContainsDuplicates(Integer: array[])
    // Loop over all of the array's items.
    For i = 0 To <largest index>
        For j = 0 To <largest index>
        // See if these two items are duplicates.
        If (i != j) Then
            If (array[i] == array[j]) Then Return True
        End If
        Next j
    Next i

    // If we get to this point, there are no duplicates.
    Return False
    End ContainsDuplicates

and then there is the other shared here as:

Boolean: ContainsDuplicates(Integer: array[])
    // Loop over all of the array's items except the last one.
    For i = 0 To <largest index> - 1
        // Loop over the items after item i.
        For j = i + 1 To <largest index> N
            // See if these two items are duplicates.
            If (array[i] == array[j]) Then Return True
        Next j
    Next i

    // If we get to this point, there are no duplicates.
    Return False
End ContainsDuplicates

Полагаю, оба результата одинаковы, т. Е. N², верно?

0 голосов
/ 04 июля 2018
  • первый цикл: от 1 до N
  • второй цикл: от 2 до N
  • третий цикл: от 3 до N ...
  • до последнего цикла: от N-2 до N
  • последний цикл: от N-1 до N

Вы видите какую-либо картину? Это как делать 1 + 2 + 3 + ... + (N-1) + N

Формулы для достижения этой цели (N + 1) (N) / 2

В обозначении Big O это эквивалентно N²

...