Big-O Notation이란? Gustafson's Law란?Amdahl’s Law란? [빅오, 구스타프슨, 암달의 법칙]

작업을 처리할 때, '어떤 도구를 사용하고, 어떤식으로 일을 하느냐'에 따라 작업 시간이 달라집니다. Software 세계에서는 작업 처리량의 효율을 나타내는 Big-O Notation라는 것이 있습니다.

이 Big-O 복잡도가 성능을 좌우하는 핵심 요소입니다. 특히, 병렬 컴퓨팅이 대세로 자리 잡은 오늘날, 효율적인 알고리즘과 하드웨어 자원의 최적화는 더욱 중요해졌습니다.

하지만, 우리는 병렬화의 한계를 무시하고 성급히 결론을 내리는 경우가 많습니다. 본 글에서는 Big-O 복잡도와 Amdahl’s Law를 중심으로 효율적인 알고리즘 선택의 중요성을 다루고, AI/ML의 새로운 가능성을 탐구해 보겠습니다.

Big-O 복잡도의 기본 이해 Big-O는 알고리즘이 수행하는 작업량을 문제 크기(n)에 따라 설명하는 표기법입니다. n 앞에 상수는 무시합니다. 예를들어 반복문 없이 평문으로 그냥 한번에 끝나는 간단한 프로그램의 경우 O(1) 반복문 하나가 들어있다면 O(n) 반복문이 각각 두...