Java 입출력과 시간 복잡도, 입/출력 시간 비교

 

선요약

• Java에서 String 의 += 연산은 O(N+K) 이다
• Java의 경우 StringBuilder 를 이용해야 한다

 

---

Java 입출력

• Java는 입력은 Scanner, 출력은 System.out을 사용한다.
     Scanner sc = new Scanner(System.in);
• 입력이 많은 경우에는 속도가 느리기 때문에, BufferedReader를 사용한다.
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
• 출력이 많은 경우에는 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한 번만 사용하거나
• BufferedWriter를 사용한다.

 

---

시간 복잡도

시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초정도이다.
이 값은 대략적인 값으로, 실제로 구현해보면 1억을 조금 넘어도 1초 이내에 수행이 가능하다

• 1초가 걸리는 입력의 크기
• O(1)
• O(lgN)
• O(N):1억
• O(NlgN):5백만
• O(N^2):1만
• O(N^3): 500
• O(2^N): 20
• O(N!): 10

 

 

---

입력 속도 비교

10,000이하의 자연수 10,000,000개가 적힌 파일을 입력받는데 걸리는 시간

 

 

---

출력 속도 비교

1부터 10 ,000 ,000까지 자연수를 한 줄에 하나씩 출력하는 시간