Jamsdhaid Ответов: 1

Количество первичных операций

Я новичок в разработке и анализе алгоритмов. У меня есть вложенный цикл и оператор and if.Я не могу определить примитивные операции, выполняемые в операторе if. Это утверждение таково

для (i=0;i<n;i++)
для(j=0;j<n;j++)
если(i!=j и A[i]==A[j])
дубликат=true
перерыв;
если(дубликат)
перерыв;

Что я уже пробовал:

я определяю No операций в операторе if следующим образом:

Доступ к элементу массива 2 раза
сравнение i и
Сравнение A[i] и A[j]
Сравнение и оператор
все это делается N раз. Правильно ли я угадываю количество примитивных операций в операторе if? если нет, то, пожалуйста, помогите мне исправить это. Заранее спасибо

1 Ответов

Рейтинг:
5

Richard MacCutchan

Это довольно просто, если мы добавим еще несколько пробелов и скобок:

if ( (i != j) and (A[i] == A[j]) )
         v     v         v
         |     |         +-----> equality operator comparing two array objects
         |     +---------------> AND logical operator testing if both expressions are true
         +---------------------> inequality operator comparing i and j

- первый тест, Если i не равно j.
- если это так, то оператор AND означает, что мы должны проверить следующее выражение
- проверить, равен ли элемент массива A[i] A[j]
- Если оба истинны, то истинно и все выражение в целом

Jamsdhaid

@Richard не будет ли это стоить за доступ к элементам массива?
затем по верхним петлям. какие могут быть сложности? Не могли бы вы прояснить ситуацию? а что, если 1-е условие ложно?

Richard MacCutchan

Что вы имеете в виду под этим "какова может быть его сложность"?
Существует два цикла: внешний перебирает все элементы массива. Внутренний цикл делает то же самое, и всякий раз, когда два индекса различны, код сравнивает элементы. Если они одинаковы, то он устанавливает duplicate=true Однако это говорит только о том, что у вас есть один или несколько дубликатов, а не точно, сколько их и где они находятся.

Jamsdhaid

Извиняюсь. это не сложность. Но я пытаюсь спросить, не будет ли это стоить для доступа к массиву как A[i] и A[j], где и i, и j имеют разные значения.
если это будет стоить для доступа к массиву больше, то какова будет его временная сложность.

0x01AA

Похоже, вы спрашиваете об оценке короткого замыкания, которую поддерживает большинство компиляторов. Вы можете прочитать об этом здесь: Оценка короткого замыкания - Википедия[^]

В случае, если i и j одинаковы, i!= j становится ложным, и поэтому связный член и не будет оцениваться, потому что результат уже завершен. Так что никакого доступа A[i], A[j] в этом случае нет.

Jamsdhaid

Какова будет стоимость оператора if. Это будет п*ц ?

Richard MacCutchan

Да, но помните, что на каждой итерации внутреннего цикла есть один случай, когда i и j равны, поэтому он не будет вычислять второе выражение.

Jamsdhaid

если он не оценит 2-ю порцию. тогда в чем же его сложность? будет ли это n^2-n ?
если да, то какой из них я должен использовать в своем анализе?

Richard MacCutchan

Извините, без понятия; это математика, а не Программирование.

Jamsdhaid

окей. спасибо за ваше время

CPallini

Сложность составляет O(n2) независимо от "стоимости доступа к массиву", "ярлыков булевых выражений" или чего-то еще.

Jamsdhaid

или это будет n+n+n? поскольку в этом заявлении выполняются три операции

Richard MacCutchan

Внешний цикл повторяет массив один раз, то есть выбирает каждый элемент массива. Внутренний цикл повторяет массив один раз для каждой итерации внешнего цикла. Поэтому время, затраченное внутреннего цикла равно N (элементов), умноженное на N (внешних итераций).