LimeCoding

앞선 포스팅에서 Big-O표기법에 대해 간략하게 설명한 적이 있다. 여기서는 Big-O표기법에 대해 좀 더 자세한 설명과 함께 Big-O표기법을 나타내는 대표적인 함수와 여러가지 연산 규칙에 대해 설명 하려고 한다. Big-O 표기법이란?(what is Big-O notation?) Big-O 표기법은 알고리즘의 점근적 상한을 나타내는 표기법이다. 즉, 알고리즘이 최악의 상황에서 작동할 경우, 표기한 증가 함수와 유사한 방식으로 증가함을 나타내는 것이다. Big-O 표기법의 수학적 정의는 다음과 같다. 정의 n ≥ n0인 모든 n에 대해 f(n) ≤ c · g(n)를 만족하는 양의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다. 정의를 좀 더 쉽게 이해하기 위해서 예시를 통해 정의를 설명해 보..

알고리즘 성능 분석 (Performance Evaluation of Algorithm) 알고리즘은 문제 해결을 하기 위한 레시피와 같다. 그러나 레시피는 세상에 하나만 존재하지는 않는다. 음식을 만들 때 각자의 방식이 있듯이 하나의 문제에 대한 알고리즘도 다양하게 나올 수 있다. 우리가 1부터 100을 더할 때 정말로 1부터 100을 다 더할 수 있지만 공식을 통해 빠르게 풀어낼 수도 있다. 다양한 알고리즘들 중에 문제를 비효율적으로 해결하는 알고리즘을 가지고 문제를 해결하고 싶은 사람은 없을 것이다. 그렇기에 어떤 기준을 가지고 알고리즘을 평가하게 되는데 그 기준이 공간 복잡도(space complexity)와 시간 복잡도(time complexity)이다. 공간 복잡도(Space Complexity)..

컴퓨터에서의 데이터 표현 방법(Data representation in computer) 컴퓨터는 기본적으로 0와 1을 통해 데이터를 표현한다. 문자, 숫자는 모두 0과 1로 표현되며 특정 규칙을 통해 해석을 할 때 그 의미를 갖는다. 예를 들어 컴퓨터 과학에서 offset이라는 단어는 기준이 되는 주소에서 해당 주소가 얼마나 떨어져 있는지에 대한 변위차를 가리키는 단어이지만 일반적인 영어에서는 '상쇄하다'라는 뜻으로 사용된다. 여기서 특정 규칙은 컴퓨터 과학에서 단어의 의미와 일반적인 영어에서의 의미이다. 0과 1을 나타내는 기준 단위는 비트(bit)이다. 이 비트들이 4개가 되면 니블(nibble)이 되고 8개가 되면 바이트(byte)가 된다. 존 형식과 팩 형식(Zoned Decimal Format..