수행시간 측정

문제

주어진 2가지 알고리즘을 비교하고, 실제 수행시간 차이가 나는 이유를 주석으로 설명하시오.

뼈대코드

  1. public class Sum {
  2. public static void main(String[] args) {
  3. int[] sampleCounts = { 1, 10, 100, 1000, 10000, 100000 };
  4. long start = 0;
  5. long end = 0;
  6. int sum = 0;
  7. for (int n : sampleCounts) {
  8. System.out.println("=================================");
  9. // sumA(n)
  10. start = System.nanoTime();
  11. sum = sumA(n);
  12. end = System.nanoTime();
  13. System.out.printf("sumA(%d): %d ns\n", sum, end - start);
  14. // sumB(n)
  15. start = System.nanoTime();
  16. sum = sumB(n);
  17. end = System.nanoTime();
  18. System.out.printf("sumB(%d): %d ns\n", sum, end - start);
  19. }
  20. }
  21. private static int sumA(int n) {
  22. return n * (n + 1) / 2;
  23. }
  24. private static int sumB(int n) {
  25. int sum = 0;
  26. for (int i = 1; i <= n; i++) {
  27. sum += i;
  28. }
  29. return sum;
  30. }
  31. }

출력 예

  1. =================================
  2. sumA(1): 6305 ns
  3. sumB(1): 9714 ns
  4. =================================
  5. sumA(55): 1005 ns
  6. sumB(55): 1398 ns
  7. =================================
  8. sumA(5050): 769 ns
  9. sumB(5050): 3229 ns
  10. =================================
  11. sumA(500500): 1135 ns
  12. sumB(500500): 43411 ns
  13. =================================
  14. sumA(50005000): 742 ns
  15. sumB(50005000): 204282 ns
  16. =================================
  17. sumA(705082704): 718 ns
  18. sumB(705082704): 2966879 ns

힌트

시간 복잡도

  1. O(1) < O(N) < O(logN) < O(NlogN) < O(N^2) < O(N^3) < O(2^N)
관련 강의로 이동

코드: java 1.8

public class Main {
public static void main(String[] args) {
}
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

입력

정답이 궁금하다면? 코드를 제출해보세요!