Большая сложность вложенного цикла в зависимости от изменения результата дроби

Question

Будучи относительно новым для Big-Oh системы обозначений и анализа сложности, меня попросили определить временную сложность Big-Oh (самая жесткая верхняя граница) следующего кода.

Теперь, насколько я могу судить,для каждой итерации после самой первой (для которой она будет выполняться только один раз) внутренний цикл выполняется x2, то есть x раз.Само по себе это будет O (x).

y никогда не изменяется в течение всего выполнения алгоритма.Тем не менее, n увеличивается на каждой итерации, что влияет на условие выхода из внешнего цикла.

Из-за постоянного увеличения n дробь, служащая условием выхода из внешнего цикла, становится все меньше и меньше.

Теперь, если было что-то вроде y / = 2, а не y/ n, каждый раз, я бы сразу переходил к O (log y) времени выполнения внешнего цикла, но из-за меняющегося знаменателя я думаю, что мы могли бы рассматривать это как фактор, который - согласно тому, что я знаюо Big-Oh-- можно игнорировать, следовательно, O (y) сложность внешнего цикла, что означает O (x * y) сложность всего метода.

Может ли кто-нибудь дать мне какое-нибудь руководство или несколькосоветы по этому поводу?Любая помощь будет принята с благодарностью.
Большое спасибо!

    void a (long x, long y){
      long n = 0, x2 = n;
      do {
        do {
          x2--;
        } while (x2 > 0);
       n++;
       x2 = x;
      } while (n < y / n);
   }

РЕДАКТИРОВАТЬ: Спасибо всем за помощь мне.Так же, как маленький дополнительный вопрос: что было бы большой сложностью, если бы код был написан так:

    void a(int x, int y) {
        int n = 1;
        do {
            x++;
            n++;
        } while(y/n > x);
    }

Я попытался немного переставить его (например, y> n * x) идумать о n как о константе, которую можно отбросить, что привело меня к мысли, что это будет O (y), но я чувствую, что есть кое-что, чего я просто еще не понимаю, о том, как эти дробные условия могут быть выражены в больших обозначениях O,

Answer 1

Может ли кто-нибудь дать мне несколько советов или несколько советов по этому поводу?

Если сомневаетесь, подсчитайте выполненные операции.

Для целей анализа сложности ¹ , это безопасное предположение, что любая примитивная операция (арифметическая, тестовая, ветвящаяся) занимает постоянное количество времени.Для этих целей вы также можете предположить, что все примитивные операции занимают одно и то же время.Так что просто сложите их все.

Затем составьте алгебраическую формулу для числа операций, выполняемых как функция ваших переменных;например, ваши x и y.

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

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

---

^{1 - Это относится только к анализу сложности.Если вы пытаетесь оценить производительность, эти предположения не верны.Разные операции занимают разное время, а в некоторых случаях время, затрачиваемое на данную операцию, может варьироваться в зависимости от контекста;например, есть ли у вас попадание в кеш.Это одна из причин того, что даже приблизительно точные априорные оценки производительности действительно тяжелая работа.}

Answer 2

Предполагая, что функция на самом деле выполняется так, как написано, внешний цикл выполняется пропорционально sqrt(y) раз, поэтому сложность всей функции составляет O(x * sqrt(y)).

(Стоит отметить, что в реальной жизни,поскольку у функции нет побочных эффектов, оптимизирующий компилятор, вероятно, заменит ее функцией, которая ничего не делает.)