1. 자료구조

자료 구조는 크게 위와같이 3가지 종류로 이루어져있다.

경우에 따라서 4가지로 나뉠수 있지만 일단 여기선 3가지로 배우겠다.

선형 구조

한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다.

선형 구조에 해당하는 자료구조는 배열, 연결 리스트, 스택, 큐 등이 있다.

비선형 구조

원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다.

비선형 구조에 해당되는 자료구조는 트리와 그래프 등이 있다.

선형 구조와 다르게 하나의 원소가 여러개의 원소와 관계를 가질 수 있다.

컴퓨터 폴더구조, 인간 관계를 표현하기에 적합하다.

마무리

더 좋고 더 나쁜 자료구조는 없다.

특정 상황에서 유용한 자료구조와 덜 유용한 자료구조가 존재할 뿐이다.

우리는 상황에 맞게 적절한 자료구조를 선택하면 된다.

시간 복잡도

알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 라는 말이다.

효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다.

Big-O Notation

우리는 프로그램의 성능을 정확하게 알 수 있을까?

일단 프로그램의 정확한 성능을 측정하기 위해서는 고려해야할것들이 아주 많다.

ex) 입력 크기, 하드웨어 성능, 운영체제 성능, 컴퍼일러 최적화, 비동기 로직 등등…

만약 항상 같은 데이터를 쓰고 같은 하드웨어 같은 성능측정 프로그램을 써도 항상 같은 결과가 나오진 않는다.

실행환경과 메모리 사용량에 따라 다른 결과가 나오기 때문이다.

따라서 프로그램의 성능을 정확히 파악하는 것은 불가능하다고 볼 수 있다.

그렇기 때문에 컴퓨터 과학자들은 대략적인 성능을 비교하기 위한 상대적인 표기법을 사용하기러 하였다.

그것이 바로 Big-O notation(빅오 표기법) 이다.

Big-O 표기법은 시간 복잡도를 나타내기 위한 방법 중 하나이다.

상수 시간 < 로그 시간 < 선형 시간 < 선형 로그 시간 < 2차 시간 < 지수 시간 < 팩토리얼 시간

이라고 부른다.

참고로 로그의 밑은 2 이다.

컴퓨터 과학에서 밑을 생략하면 기본적으로 2라고 생각하면 된다.

이 Big-O 표현을 코드로 나타내면 아래와 같다.

위의 이미지상 윗줄의 예처럼 Big-O 표기법에선 식에 계수를 붙이거나 상술르 더하고 빼는건 있을 수 없다.

왜냐하면 Big-O 표기법은 점근적 표기법을 따르기 때문이다.

점근적 표기법이란 함수의 증감추세를 비교하는 방법이다.

즉, 점근적 표기법이란 n을 무한대로 주었을 때 근사하게 되는지를 분석하여 표기하는 벙식이다.

Big-O 표기법의 법칙

뭐 이런 저런 여러가지 법칙이 있지만 가장 중요한건 아래의 2가지 이다.

참고
3. 시간복잡도