временная сложность оператора if else c# - PullRequest
Новая
       47

временная сложность оператора if else c#

2 голосов
/ 29 мая 2020

Какой из следующих двух более эффективен с точки зрения сложности обработки / времени - извините, просто пытаюсь осознать сложность времени и возможное влияние на время компьютерной обработки:

Вариант 1 

if (condition1) {
  function1();
  function2();
} 
else {
  function3();
}

Вариант 2 

if (condition1) {
  function1();
}
else {
  function3();
}

if (condition1) {
  function2();
}
else {
  function3();
}

Предполагая, что function1 () и function2 () оба являются O (N), я думаю, что вариант 1 и вариант 2 имеют временную сложность O (N). Однако, если бы мы могли измерить, насколько быстро оба варианта работают на одном компьютере, будет ли вариант 1 быстрее или разница будет минимальной?

Спасибо!

Ответы [ 2 ]

3 голосов
/ 29 мая 2020

Временная сложность if постоянна, то есть O (1). Такова сложность двух if.

Если функции - O (N), сложность в целом составляет O (N).

Время Сложность не показатель эффективности, а масштабируемости. Он не говорит, сколько ресурсов (циклов процессора, памяти и т. Д.) Требуется алгоритму, но сколько больше он захватит, если вы удвоите размер ввода.

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

Что касается фактической разницы в производительности:

Вариант 2 вызовет function3() два раза, поэтому сравнение зависит от этого.

Если функции имеют какое-либо значение обработка, разница между двумя вариантами будет незначительной, в ней будут преобладать колебания функций.

Как правило, выполнение тривиальных операций (например, if) не может обсуждаться без контекста.

Для условных переходов главный вопрос: насколько они предсказуемы?
то есть, большую часть времени они используют одну и ту же ветвь? Два хорошо предсказуемых условных перехода намного лучше, чем один плохо предсказанный.

1 голос
/ 29 мая 2020

Вариант 2 не может быть быстрее, чем Вариант 1, поскольку он выполняет как минимум столько же работы, чтобы выяснить, какие функции вызывать. Также обратите внимание, что вариант 2 приводит к двум вызовам функции 3, когда условие1 ложно, поэтому в этом случае он выполняет вдвое больше работы (при условии, что функция выполняет гораздо больше работы, чем показанные фрагменты, которые просто определяют, какие функции вызывать).

На практике они, вероятно, будут иметь точно такую ​​же производительность (игнорируя повторный вызов функции 3), потому что оптимизирующий компилятор распознает возможность визуализации двоичного кода для варианта 2, который намного больше похож на то, что вы ожидайте вариант 1. При отсутствии оптимизаций вы видите еще одну условную ветвь, которую, как я думаю, при разумных предположениях можно смело охарактеризовать как минимальное количество дополнительных накладных расходов. Теперь, если бы это было в жестком l oop, оптимизации были бы отключены, а condition1 практически всегда было ложным, тогда, возможно, вы бы увидели больше проблемы (из-за многих пропущенных предсказаний ветвлений, прерывающих конвейер), но я сомневаюсь в этом.

...