Как понять обозначение Big O в данном примере
Вы сказали, что не хотите иметь оператор switch. Я понимаю, что у этого есть переключатель, но если у вас должно быть три разные переменные, вы можете инкапсулировать свой коммутатор внутри вызова функции:
string message1 = null;
string message2 = null;
string message3 = null;
void SetMessage(int i, string value)
{
if(i == 1)
message1 = value;
etc
}
for (int i = 1; i <=3; i++)
{
SetMessage(i, "blabla" + i.ToString());
}
Не оптимальное решение, но если вы ДОЛЖНЫ иметь отдельные переменные, это будет скрыть беспорядок.
2 ответа
Я думаю, что вы путаетесь между тета-нотацией и большой буквой О.
Тета-нотация определяет приблизительную оценку времени работы алгоритма, в то время как Big O-нотация определяет наихудшее время работы алгоритма.
Метод, который вы упомянули выше, используется для вычисления тэты, а не большой О. Большой O из вышеупомянутой проблемы может быть O (n ^ 4), O (n ^ 5), O (n ^ 6) и так далее ... все правильные значения. Но для тэты только тэта (n ^ 3) верна.
Это в O (n ^ 3), но O (n ^ 4), O (n ^ 5) и т. Д. Является надмножеством O (n ^ 3), поэтому, если что-то есть в O (n ^ 3) тогда оно также может быть в O (n ^ 100). Лучший ответ и тот, который используется по соглашению, это наименьший большой O, к которому он принадлежит, то есть O (n ^ 3), но это не единственный.