Какова временная сложность моей функции?

Ответ 1

Внешний цикл выполняет n раз.

Для каждой итерации внутренние циклы выполняются n / i раз.

Общее количество прогонов:

n + n/2 + n/3 + ... + n/n

Асимптотически (игнорируя целочисленное арифметическое округление), это упрощается как

n * (1 + 1/2 + 1/3 + ... + 1/n)

Эта серия слабо сходится к n * log(n).

Следовательно, сложность O (N.log(N)), как вы ожидали.

Ответ 2

Первый внутренний цикл выполняется n раз Второй внутренний цикл выполняется n/2 раз Третий внутренний цикл выполняет n/3 раз .. Последний выполняется один раз

Итак n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n).

Это n умножается на сумму гармонических рядов, которая не имеет хорошего закрытого представления формы. Но, как показано здесь, это O(log(n)). Таким образом, в целом алгоритм O(n log(n))

Ответ 3

В качестве альтернативы используйте переменную подстановку y = n - x, за которой следует нотация Sigma, чтобы проанализировать количество итераций внутреннего цикла while вашего алгоритма.

Вышеперечисленное переоценивает для каждого внутреннего цикла while число итераций на 1 для случаев, когда n-1 не кратно i, то есть где (n-1) % i != 0. По мере того как мы продолжим, будем считать, что (n-1)/i является целым числом для всех значений i, поэтому переоценивает общее число итераций во внутреннем цикле while, впоследствии включающее знак меньше или равно в (i) ниже, Перейдем к анализу сигма-нотации:

где we, at (ii), аппроксимировали связанный интеграл n: th гармоническое число. Следовательно, алгоритм работает в O(n·ln(n)), асимптотически.

Оставив асимптотическое поведение и изучая фактический рост алгоритма, мы можем использовать хорошие данные выборок точных (n,cnt) (где cnt - число внутренних итераций) парами @chux (см. его ответ) и сравнить с оцененным числом итераций сверху, т.е. n(1+ln(n))-ln(n). Очевидно, что оценка гармонично согласовывается с фактическим счетом, см. Графики ниже или этот фрагмент для фактических номеров.

Наконец, заметим, что если в сумме над 1/i n->∞ положить n->∞, то полученная серия представляет собой бесконечную гармоническую серию , которая есть, как ни странно, расходятся. В доказательстве последнего используется тот факт, что в бесконечной сумме ненулевых членов естественно бесконечно бесконечно. На практике, однако, при достаточно большом, но не бесконечном n ln(n) является подходящим приближением суммы, и эта расходимость здесь не имеет отношения к нашему асимптотическому анализу.

Ответ 4

Попытка этого путем тестирования и графики. Строка log2 vs log2 выглядит довольно линейно. Что-то между более чем линейным O (n) и меньше O (n * log (n)). "Нарисуй" свой собственный вывод.

[изменить]

Используя математические производные формулы, вычисленная O() является верхней границей O (n * log (n)). Это использует "доли итераций цикла", которые увеличивают счет на долю, а не 1. Например. Когда n равно 6, количество итераций равно 6 + 3 + 2 + 1,5 + 1,2 + 1 = 14,7, а не фактическое 6 + 3 + 2 + 2 + 2 + 1 = 16. Это отличие относительно менее значимо как n увеличивается, таким образом, немного меньше, чем O (n * log (n)) роста. Поэтому, не игнорируя код, используется целочисленная математика, у нас есть гораздо более сложный вопрос.

unsigned long long what(int n) {
  unsigned long long cnt = 0;
  int i;
  for (i = 1; i <= n; i++) {
    int x = n;
    while (x > 0) {
      x -= i;
      cnt++;
    }
  }
  return cnt;
}

void wtest(int n) {
  unsigned long long cnt = what(n);
  printf("%d %llu\n", n, cnt);
  fflush(stdout);
}

void wtests(void) {
  int i = INT_MAX/2 + 1;
  while (i > 0) {
    wtest(i);
    i /= 2;
  }
}

int main(void) {
  wtests();
  return 0;
}

Выход

1073741824 23567395117
536870912 11411566988
268435456 5519718329
134217728 2666826555
67108864 1286897093
33554432 620190504
16777216 298466265
8388608 143418602
4194304 68802063
2097152 32947406
1048576 15746897
524288 7510048
262144 3573331
131072 1695816
65536 802493
32768 378537
16384 177921
8192 83286
4096 38803
2048 17973
1024 8275
512 3782
256 1713
128 765
64 337
32 145
16 61
8 24
4 9
2 3
1 1