Написание тестовой программы для оценки сложности вычислений (Big O)

Question

У меня была задача написать тестовую программу для оценки вычислительной сложности (Big O) следующей задачи, и я действительно не знаю, с чего начать.

1. Один цикл повторяется n раз
2. Вложенный цикл, в котором цикл eaach повторяется n раз

Это то, что я смог создать

for(int i=0; i <n; i++){
   // Do stuff
}

Теперь проблема в том, как написатьТестовая программа.Кто-нибудь может мне помочь?

Answer 1

Для задач со сложностями вида (n ^ k), где k> = 0, код может быть записан путем подсчета количества вложенных циклов.Но это трудно реализовать в рекурсивных задачах со "сложными" сложностями ((n ^ 2) * lg (n)).

Я не реализовал это, но я уверен, что это можно сделать

Answer 2

Из того, что вы описали, сложность алгоритма выглядит как O (n ^ 2).Можно попытаться оценить его «экспериментально»: просто запустите алгоритм с различными значениями n и возьмите время вычисления.Затем нанесите значения n на оси x графика и значения времени на оси y.Теперь вы должны увидеть что-то приближенное с параболой.