Является ли этот алгоритм O (N) на самом деле O (logN)? - PullRequest
Новая
       1

Является ли этот алгоритм O (N) на самом деле O (logN)?

1 голос
/ 17 января 2020

У меня есть целое число N. Я обозначаю f [i] = количество появлений di git i в N. Теперь у меня есть следующий алгоритм.

FOR i = 0 TO 9 FOR j = 1 TO f[i] k = k*10 + i;

Мой учитель сказал, что это O (N). Мне кажется, это больше похоже на алгоритм O (logN). Я что-то пропустил?

Ответы [ 3 ]

1 голос
/ 17 января 2020

Временная сложность алгоритма обычно измеряется как функция от размера ввода. Ваш алгоритм не принимает N в качестве входных данных; входные данные выглядят как массив f. Есть еще одна переменная с именем k, которую ваш код не объявляет, но я предполагаю, что это недосмотр, и вы намеревались инициализировать, например, k = 0 перед первым l oop, так что k не является входом для алгоритм.

Внешний l oop выполняется 10 раз, а внутренний l oop запускается f[i] раз для каждого i. Поэтому общее число итераций внутреннего l oop равно сумме чисел в массиве f. Таким образом, сложность может быть записана как O(sum(f)) или O(Σf), где Σ является математическим символом для суммирования.

Поскольку вы определили, что N является целым числом, которое f считает цифры, фактически можно доказать, что O(Σf) - это то же самое, что и O(log N), при условии, что N должно быть положительным целым числом. Это потому, что Σf равно количеству цифр, которое имеет N, что приблизительно равно (log N) / (log 10). Итак, по вашему определению N, вы правы.

Я предполагаю, что ваш учитель не согласен с вами, потому что они думают, что N означает что-то еще. Если ваш учитель определяет N = Σf, то сложность будет O(N). Или, возможно, ваш учитель допустил настоящую ошибку; это не невозможно. Но первое, что нужно сделать, это убедиться, что вы согласны со значением N.

1 голос
/ 17 января 2020

Я думаю, что вы и ваш учитель говорите одно и то же, но это сбивает с толку, потому что целое число, которое вы используете, называется N, но также часто называют алгоритм, линейный по размеру входных данных, как O(N). N перегружается в виде указанного c имени и общего числа c. * а затем их частоты в f. Например, мы могли бы иметь: 

   Z = 12321
   d = [1,2,3,2,1]
   f = [0,2,2,1,0,0,0,0,0,0]

Тогда стоимость прохождения всех цифр в d и вычисления количества для каждой будет O( size(d) ) = O( log (Z) ). Это в основном то, что ваш второй l oop делает наоборот: он выполняется один раз для каждого вхождения каждой цифры. Итак, вы правы, что здесь происходит что-то логарифмическое c - число цифр Z равно логарифмическому c в размере Z. Но ваш учитель также прав, что здесь происходит что-то линейное - подсчет этих цифр является линейным по количеству цифр.

0 голосов
/ 17 января 2020

Я нахожу ваше объяснение немного запутанным, но давайте предположим, что N = 9075936782959 является целым числом. Then O(N) на самом деле не имеет смысла. O(length of N) имеет больше смысла. Я буду использовать n для длины N.

Затем f(i) = итерация по каждому числу в N и сумма, чтобы найти, сколько раз i находится в N, что делает O(f(i)) = n (это линейно). Я предполагаю, что f (i) - это функция, а не массив.

Ваш алгоритм цикличен не более:

  • 10 раз (первый l oop)
    • от 0 до n раз, но общая сумма равна n (сумма f(i) для всех цифр должна составлять n)

Заманчиво сказать, что Тогда алгоритм равен O(algo) = 10 + n*f(i) = n^2 (исключая константу), но f(i) вычисляется только 10 раз, каждый раз, когда вводятся вторые циклы, поэтому O(algo) = 10 + n + 10*f(i) = 10 + 11n = n. Если f (i) - массив, это постоянное время.

Я уверен, что не видел проблему так же, как вы. Я все еще немного озадачен определением в вашем вопросе. Как ты придумал log(n)?

...