Какова временная сложность этого алгоритма

Напишите программу, которая принимает целое число и выводит все способы умножения меньших целых чисел, которые равны исходному числу, без повторения множества факторов. Другими словами, если ваш вывод содержит 4 * 3, вы не должны снова распечатывать 3 * 4, так как это будет повторяющийся набор. Обратите внимание, что это не требует только простой факторизации. Кроме того, вы можете предположить, что целые числа ввода являются разумными по размеру; правильность важнее эффективности. PrintFactors (12) 12 * 1 6 * 2 4 * 3 3 * 2 * 2Какова временная сложность этого алгоритма

public void printFactors(int number) { 
    printFactors("", number, number); 
} 

public void printFactors(String expression, int dividend, int previous) { 
    if(expression == "") 
     System.out.println(previous + " * 1"); 

    for (int factor = dividend - 1; factor >= 2; --factor) { 
     if (dividend % factor == 0 && factor <= previous) { 
      int next = dividend/factor; 
      if (next <= factor) 
       if (next <= previous) 
        System.out.println(expression + factor + " * " + next); 

      printFactors(expression + factor + " * ", next, factor); 
     } 
    } 
}

Я считаю, что

Если данное число равно N, а число простых множителей N = д, то сложность времени равна O (N^d). Это связано с тем, что глубина рекурсии будет увеличиваться до числа простых факторов. Но это не сложно. Какие-либо предложения?

источник

2016-08-15 user12331

Я не думаю, что код работает. Например: 'nextnext' не определен. –

@PaulHankin. К сожалению, это была опечатка. Исправлено: – user12331

дубликат http://stackoverflow.com/questions/38949619/confusion-related-to-the-time-complexity-for-this-algorithm –

2 идеи:

Алгоритм чувствителен к выходу. Выведение факторизация израсходовал на большинстве O (N) итераций цикла, так что в целом мы имеем O (N * number_of_factorizations)

Кроме того, с помощью теоремы Учителя, уравнение: F(N) = d * F(N/2) + O(N), поэтому в целом мы имеем O(N^log_2(d))

источник

2016-08-17 17:03:24 maniek

Почему d * F (N/2), это потому, что в худшем случае фактор может разделить исходное число на половину и есть d простых факторов. Кроме того, согласно основной теореме d не может быть больше 2. Также откуда происходит O (N)? Это потому, что в худшем случае оно может быть кратным N чисел? – user12331

@ user12331 Вы правы относительно причины для d * F (N/2). [Случай 1] (https://en.wikipedia.org/wiki/Master_theorem#Case_1) пример говорит, что 'a' может быть 8, поэтому неверно говорить, что оно не может быть больше 2. O (N) потому что цикл for повторяется вокруг N раз. – maniek

BTW, первая граница жестче, потому что число факторизации не растет быстрее, чем O (N) (доказательство?), Поэтому в целом оно не хуже O (N^2). Кроме того, я чувствую, что это действительно O (N log N) в худшем случае, но не может доказать это сейчас. – maniek

сложность времени должно быть:

number of iterations * number of sub calls^depth

Есть O (N журнал) суб вызовы вместо O (N), так как the number of divisors of N is O(log N)

T глубина рекурсии также равна O (log N), а количество итераций для каждого рекурсивного вызова меньше N/(глубина 2), поэтому общая временная сложность равна O (N ((log N)/2)^(log N))

источник

2016-08-21 06:10:53 DarkKnight

The time complexity is calculated as : Total number of iterations multiplied 
by no of sub iterations^depth.So over all complexity id Y(n)=O(no of 
dividends)*O(number of factorization)+O(no of (factors-2) in loop); 

Example PrintFactors(12) 12 * 1 ,6 * 2, 4 * 3, 3 * 2 * 2 
O(no of dividends)=12 
O(number of factorization)=3 
O(no of factors-2){ in case of 3 * 2 * 2)=1 extra 

Over all: O(N^logbase2(dividends))

источник

2016-08-23 21:13:12

Какова временная сложность этого алгоритма

ответ

Смежные вопросы