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

Вот код:

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)

Alexander Ivanchenko 21.11.2022 17:50
LeetCode запись решения 2536. Увеличение подматриц на единицу
LeetCode запись решения 2536. Увеличение подматриц на единицу
Увеличение подматриц на единицу - LeetCode
Версия Java на основе версии загрузки
Версия Java на основе версии загрузки
Если вы зайдете на официальный сайт Spring Boot , там представлен start.spring.io , который упрощает создание проектов Spring Boot, как показано ниже.
Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot
В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .
Как включить TLS в gRPC-клиенте и сервере : 2
Как включить TLS в gRPC-клиенте и сервере : 2
Здравствуйте! 🙏🏻 Надеюсь, у вас все хорошо и добро пожаловать в мой блог.
Сортировка hashmap по значениям
Сортировка hashmap по значениям
На Leetcode я решал задачу с хэшмапой и подумал, что мне нужно отсортировать хэшмапу по значениям.
1
1
63
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

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

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). раз. Лучше оставаться формальным, чтобы избежать путаницы.

Berthur 21.11.2022 18:03

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

maio290 21.11.2022 18:14
Ответ принят как подходящий

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

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

  • Самый внешний цикл - O(n)

  • Второй цикл - O(n^2) за каждый элемент внешнего цикла

  • Самый внутренний цикл - O(n^2) за каждый элемент для второго цикла

Другие вопросы по теме