Анализ сложности выполнения функции

Question

Я написал функцию append() в Java, и мне нужно проанализировать ее сложность выполнения по O (N) и Θ (N).

Это оригинальный вопрос:

Пусть append() «ы сложности выполнения является t = O(N), это означает, что t также могут быть представлены t = C*N. (как C является постоянной)

Поэтому (t/N) = C.

Если, например, t = O(N^2), то (t/N^2) = C и так далее.

используйте этот метод, чтобы найти append() время работы.

Так что я побежал append() N раз для 3-х различных N с: 1,000, 5,000, 10,000.

long start = System.currentTimeMillis(); 
for(i = 0; i < N; ++i) { 
    append(); 
} 
long end = long start = System.currentTimeMillis(); 

System.out.println(end - start); 

и я записал end-start, который является время выполнения в миллисекундах.

Теперь, как я могу использовать эту информацию, чтобы получить совпадение времени append()?

Заранее благодарен!

Answer 1

Вы неправильно поняли метод. N должна быть длиной строки, а не количество вызовов функций Она должна быть

String str(n); // Or whatever how you create a string with n elements 

long start = System.currentTimeMillis(); 
append(); 
long end = long start = System.currentTimeMillis(); 

System.out.println(end - start); 

Затем запустить его в течение нескольких Ns, и пытается выяснить, какой раз coplexity это. Попытайтесь разделить t/N, затем t/N^2, пока вы не найдете постоянного ответа.

Answer 2

С помощью только одной точки данных вы не можете определить временную сложность функции. Хороший способ эмпирически определить временную сложность - это время работы на входах нескольких разных размеров и посмотреть на относительный темп роста времени выполнения операции. Например, если время выполнения примерно удваивается по мере удвоения размера ввода, сложность времени равна O (n). Если время выполнения примерно в четыре раза по мере увеличения размера ввода, сложность времени равна O (n).

Причина, по которой вам нужно несколько точек данных, похоже на то, почему вам нужно несколько точек, чтобы определить линию. Учитывая только один момент, вы не можете сказать, что такое наклон или перехват. При измерении временной сложности вы не можете отфильтровать относительные вклады срока действия и сроков роста.

Надеюсь, это поможет!