#time-complexity
Вопрос:
Я пытаюсь найти временную сложность по строкам кода. Однако на самом деле я этого не понимаю.
int codeMT(int n) { int a = 1; int i = 1; while (i lt; n * n) { j = 1; while (j lt; n * n * n) { j = j * 3; a = a j i; } i = i 2; } return a; } В данном случае это мой мыслительный процесс.
Во-первых, нам нужно начать с внутреннего цикла.
while (j lt; n * n * n) { j = j * 3; a = a j i; } Здесь есть j = j * 3, что делает этот журнал(n)(база журнала 3), но тогда у нас есть защита цикла, которая имеет n n n, что делает n^3. Следовательно, эта часть кода имеет логарифмическую(n^3) временную сложность.
Во-вторых, внешний цикл while имеет защиту цикла n * n, что делает его n^2.
Таким образом, O(n^2(log(n^3))
Мой подход подходит? или есть что-то, чего мне не хватает/что я мог бы улучшить свой мыслительный процесс?
Спасибо
Комментарии:
1. журнал(n^3) = 3 журнала(n), что равно O(журнал(n)), поэтому вы можете немного упростить.
2. Понятно, кажется, я понял. Итак, часть n^2 была правильной, но тогда мне нужно изменить журнал(n^3) = 3log(n) и, таким образом, постоянные падения = log(n). Итак, n^2 * log(n) = n^2log(n). Спасибо!