Data Structure & Algorithm10 메모리에 위치한 배열과 연산에 대한 Big-O value 배열에 대해 알아야 할 점을 간단히 정리해보자. 메모리에서 연속적으로 위치한다. 여기 저기 흩어져 있는 게 아니라, 한 배열의 요소들은 메모리 안에서 서로 인접해 있다. 메모리 안에 큰 블록이 생긴다고 생각할 수 있다. 배열의 길이가 한 번 정해지면 다시 수정할 수 없는 이유가 이 때문이다.한 배열 안의 모든 요소들은 같은 크기를 갖고 있다. 이를테면 int 배열이면 4바이트씩 할당된다. 만약 primitive type이 아니라 object 배열이라면 어떨까? 배열의 원소가 object라면, 사실 그건 object 자체가 아니라 object reference다. 해당 object를 참조하고 있을 뿐이다. 그러니 어떤 object를 참조하든 상관없이 배열 안에서 항상 같은 크기를 갖고 있다. 바로 이러한 .. 2018. 3. 4. Big-O Notation (빅오 표기법) 복잡도(Complexity)는 크게, 시간 복잡도 (Time Complexity) 공간 복잡도 (Memory Complexity) 의 2가지로 나눌 수 있는데, 요즘은 메모리 가격이 많이 낮아져서 공간 복잡도보다는 주로 시간 복잡도에 더 관심을 기울이는 편이다. 시간 복잡도란 즉, 어떤 알고리즘을 수행하는 데 얼마나 많은 절차(step)를 거쳐야하는지를 나타낸다. 시간 복잡도의 최선의 경우(best case)와 최악의 경우(worst case)를 생각했을 때, 최선의 경우는 별로 의미가 없다. 알고리즘을 수행할 때 최선의 경우가 발생하는 상황은 실질적으로는 드물기 때문이다. 평균(average case)도 생각해볼 수는 있겠지만 최악의 경우에 대한 유의미한 정보를 제공해주지는 않는다. 따라서 알고리즘 간.. 2018. 3. 4. 이전 1 2 다음
