시간복잡도 심화.

기존에 다룬 글은 아주 간단한 수준의 시간복잡도의 내용이였다.

조금 더 심화된 내용을 다뤄보고자 한다.

 

1초에 5억번 계산의 내용은 컴퓨터 사양의 차이가 있는듯 하다.

본인이 사용하는 컴퓨터에서 다른 3개의 프로그램이 작동되고 있었으나,

500억번 정도의 연산에 1초가 소요됐다.

 

https://github.com/kucnea/CodingTestPractice/blob/master/src/com/test/TestTime.java

GitHub - kucnea/CodingTestPractice: -

 

이 정도의 차이가 좀 의아하긴한데, 연산의 기준이 잘못됐을 수 있다.

본인은 단순히 컴퓨터가 할 하나의 연산 값을 더하는 것을 고려했지만

 

https://www.secmem.org/blog/2021/01/22/time-complexity/

 

이 글의 경우 사칙연산등으로 계산해 연산의 단위가 달랐을 수 있다.

이 글은 참고로 1초에 10억회로 보는 것이 현실성있다고 한다.

 

이하로는
( https://www.secmem.org/blog/2021/01/22/time-complexity/ )

에서 공부한 내용을 정리한 것이다.

 

시간복잡도를 계산할때 " 적어도 넘지않는다 "의 기준으로 생각해보면 좋을 듯 하다.

낮은 시간복잡도의 코드를 짰더라도, 시간복잡도의 최악의 경우를 고려해봄이 좋다.


평균 시간 복잡도와 최악의 경우 시간복잡도의 
큰 차이가 있는 대표적인 알고리즘으로 퀵소트 ( Quick Sort ) 가 있다.

퀵소트는 평균 시간 복잡도가 O(n log n) 이지만, 최악의 경우 O(n^2)이다.

단, 모든 알고리즘에 대해 최악의 경우를 고려해야하는 것은 아니다.

1. 평범한 데이터 대해 쉽게 저격되는 알고리즘 :
     퀵소트의 경우 단순한 원소가 오름차순이나 내림차순으로 정렬되어있기만해도 최악의 경우가 된다.

2. 코딩테스트를 목표로 할때, 쉽게 예측할 수 있는 저격이 가능한 알고리즘 : 
     다익스트라를 정해로 하는 문제에 SPFA ( Shortest Path Faster Algorithm ) 을 저격하는 데이터라거나,
     C++의 unordered_map의 기본 해시 함수를 저격하는 것등이 포함된다. 

3. 코드포스등에서 코드를 보고 저격이 가능한 데이터들도 있다고 하니 참고하자.



시간복잡도의 분석에 대해 알아보자

1. 상수 시간 코드 묶음 찾기.
     단순 사칙연산등
     입력과 무관하게 특정 횟수 이하로 실행하도록 설계된 루프문

2. 내장 / 라이브러리 함수의 시간복잡도
     겉으로 보이는 루프는 없으나 자체적인 시간 복잡도를 가지고 있다.
     이를 고려하지않고 설계할 경우 비효율적일 수 있다.
     예를들어 ArrayList와 LinkedList를 보자
     ( n개의 요소에서 중간 지점에 1개의 데이터를 add/get할때 )
     ArrayList
     : add(index, element) - O(n)
     : get(index) - O(1)

     LinkedList
     : add(element) - O(n)
     : get(index) O(n)

     ArrayList에서 add를 중간에 하면 특정 위치 다음의 데이터를 복사 후 한칸 뒤에 붙여야 한다. 

     shift를 해야해서 O(n)의 시간복잡도를 갖는다. LinkedList의 경우에도 

     추가할 위치를 찾기위해 처음부터 데이터를 훑어야 한다.

     이러한 것들의 자세한 공부는 이후에 하고, 

     이렇게 겉으로 보이는 루프는 없으나 자체적인 시간 복잡도는 가지고 있는 것들을 확인하자.

     코드의 시간 복잡도를 계산할때는 컴퓨터가 수행할 수 있는 기본 연산을 단위로 해야한다.
     내장 / 라이브러리가 내부적으로 가지는 구조가 무엇인지 알고, 

     구조상에서 연산들은 어떤 시간 복잡도를 가지는지 함께 공부하는 것이 좋다.

3. 루프의 시간복잡도
     중첩된 루프끼리의 시간 복잡도는 곱한다.
     중첩되지 않은 문장끼리의 시간 복잡도는 더한다.

     중첩되지 않았다면 개별적으로 실행되기에 각각의 시간 복잡도를 더하게 될 것이고,
     중첩되는 루프라면 첫 루프에서 하나의 인자가 두 번째 루프를 모두 수행하고 

     다음 인자로 넘어가는 루프가 발생하는 것으로 곱하게 된다.

4. 각 원소에 대한 연산 횟수로 시간 복잡도 계산하기
     탐색 알고리즘의 대표적인 형태인 DFS와 BFS는 

     정점의 수가 V개, 간선의 수가 E개인 그래프에 대해서 중복 방문을 하지 않을때 O(V+E)이다. 
     이들을 구현한 코드만으로는 직관적으로 이해하기 어려운데
     이때 사용할 수 있는 방법이 각 원소에 대한 연산 횟수를 세는 것이다.
     이는 추후 DFS와 BFS를 공부하게된다면 살펴보자.

5. 이러한 방법외에도 자신의 코드가 가장 오래 걸릴 것 같은 케이스를 생각해보는 방법으로 
   시간 복잡도를 계산해볼 수 있다.

     추가로 대부분의 언어 라이브러리에서 제공하는 정렬 함수는 

     최악의 경우 O(n log n) 을 보장하므로 그대로 사용하면 된다.
     예외로 Java의 Arrays.sort에 primitive type 배열을 전달하는 경우 퀵소트를 사용한다는 것이 있다.
     라이브러리를 사용하지 못하게 하는 코딩 테스트 등에서는

     구현이 쉬운 병합 정렬을 추천하며, 자신있다면 합정렬을 사용하자.

 

전체적으로 기본적인 자료구조와 메소드등을 익히고나면 시간복잡도를 정리하며 복습하는 것도 좋겠다.