Какова временная сложность для трех вложенных циклов ниже?

Вот код:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n * n; j++) {
        for (int k = 0; k < j; k++) {
            sum++;
        }
    }
}

Мне нужно оценить временную сложность в обозначении Big-O вложенных циклов выше.

Это просто O(n) * O(n) * O(n) + O(1) сделать O(n^3)? Или есть еще что-то?

Самый внутренний цикл выполняется за квадратичное время (не постоянное), поэтому должно быть O(n) * O(n^2) * O(n^2) = O(n^5)

— 21.11.2022 17:50

java algorithm big-o

21.11.2022 17:46

LeetCode запись решения 2536. Увеличение подматриц на единицу

Увеличение подматриц на единицу - LeetCode

Версия Java на основе версии загрузки

Если вы зайдете на официальный сайт Spring Boot , там представлен start.spring.io , который упрощает создание проектов Spring Boot, как показано ниже.

Документирование API с помощью Swagger на Springboot

В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .

Что происходит, когда создается объект класса в Java?

Как включить TLS в gRPC-клиенте и сервере : 2

Здравствуйте! 🙏🏻 Надеюсь, у вас все хорошо и добро пожаловать в мой блог.

Сортировка hashmap по значениям

На Leetcode я решал задачу с хэшмапой и подумал, что мне нужно отсортировать хэшмапу по значениям.

Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Второй цикл не O(n), он O(n^2) сам по себе.

21.11.2022 17:50

for (int i = 0; i < n; i++) -> runs n times.
 for (int j = 0; j < n * n; j++) -> runs n² times.
  for (int k = 0; k < j; k++) -> runs n² times (k == j == n²)

n * n² * n² = n^5.

Sum++++ является операцией постоянного времени выполнения (1) и поэтому может быть проигнорирована.

Третий цикл не выполняется n ^ 2 раза, но выполняется O (n ^ 2). раз. Лучше оставаться формальным, чтобы избежать путаницы.

— 21.11.2022 18:03

Да, формальности никогда не были моим фаворитом... Я оставлю пост как есть, думаю, вашего комментария в качестве подсказки должно быть достаточно, спасибо :)

— 21.11.2022 18:14

21.11.2022 17:51

Ответ принят как подходящий

Самый внутренний цикл выполняется за квадратичное время (не постоянное), поэтому он должен быть O(n) * O(n^2) * O(n^2) = O(n^5).

Вот все расходы: