[push_swap]

복잡도 (Complexity)

알고리즘 성능 분석을 위한 방법

시간 복잡도와 공간 복잡도가 있다.

시간 복잡도 (Time Complexity)

알고리즘을 실행할 때, 실행된 명령문의 실행 빈도수 (연산의 횟수)
-> 실행 시간으로 할 경우 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않는다.

• Best case : 최소 리소스(시간 복잡도) 사용량
• Worst case : 최악 리소스(시간 복잡도) 사용량
• Average case : 평균 리소스(시간 복잡도) 사용량

공간 복잡도 (Space Complexity)

알고리즘이 완전히 실행될 때까지 필요한 저장 공간

 

- 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어 알고리즘의 성능을 판단할 때는 시간 복잡도 위주로 판단한다.

 

빅오 표기법 (Big-O notation)

임의의 입력에 대한 복잡도 함수

시간복잡도에서는 특정 크기 입력(n)을 기준으로 실행하는 연산 횟수의 최고 차항을 O(최고 차항)으로 표기하는 방법

ex) n^2 + n => O(n^2)

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)

 

Big-O 표기법으로 나타낸 정렬 알고리즘 복잡도

정렬 알고리즘	시간 복잡도
	평균(Average)	최선(Best)	최악(Worst)
Bubble Sort	O(n^2)	O(n^2)	O(n^2)
Selection Sort	O(n^2)	O(n^2)	O(n^2)
Insertion Sort	O(n^2)	O(n)	O(n^2)
Merge Sort	O(nlogn)	O(nlogn)	O(nlogn)
Quick Sort	O(nlogn)	O(nlogn)	O(n^2)
Heap Sort	O(nlogn)	O(nlogn)	O(nlogn)
Shell Sort	O(n^(1.25))	O(n^(1.25))	O(n^(1.25))
Radix Sort	O(dn) d : 기수의 크기	O(dn)	O(dn)

 

Quick sort

• 참고 : https://www.youtube.com/watch?v=O-O-90zX-U4

swap연산의 횟수가 일정하지 않다. 최악의 경우 n^2이 나오는 것도 이때문이다.

다만 적절한 pivot을 선택하면 최대 swap 횟수가 n/2가 된다.

여기서 가장 적절한 pivot은 한 가운데에 있는 값

해당 과제에선 미리 정렬을해 인덱싱을 해둔 후 사용해도 된다고 했다. 제일 중간 값을 가지고 할 수 있다.

 

그리디 알고리즘 (Greedy Algorithm)

각 단계마다 당장 눈 앞에 보이는 최적의 상황을 선택해 결과를 도출하는 방법

 

C main함수에서 argc의 최대값

argc는 int형이므로 INT_MAX가 최대일 것이고

sysconf()에 maximum argument count가 설정되어있다고 한다

OS마다 ARG_MAX 값은 다르다고 한다.

 

참고

• https://en.wikipedia.org/wiki/Analysis_of_algorithms#Run-time_analysis
• https://dev-with-precious-dreams.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Time-Complexity%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84%EC%99%80-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95
• https://velog.io/@welloff_jj/Complexity-and-Big-O-notation
• https://en.wikipedia.org/wiki/Best,_worst_and_average_case
• https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50
• https://techdebt.tistory.com/27