버블 정렬은 단순 정렬(simple sort)중 하나로 알려져있으며 매우 기본적인 정렬 알고리즘이지만 더욱 빠르다고 알려진 정렬 알고리즘보다 비효율적이다. 버블 정렬 예제를 살펴보자. 먼저 [ 6, 3, 1, 2, 4, 5 ] 이라는 배열을 정렬하고 싶다고 가정하자. 1loop [ 6, 3, 1, 2, 4, 5 ] 먼저 6과 3을 비교하여 순서가 맞지 않음을 확인하고 6과 3을 교환한다. [3, 6, 1, 2, 4, 5 ] 그다음으로 6과 1을 비교하여 순서가 맞지 않음을 확인하고 6과 1을 교환한다. [3, 1, 6, 2, 4, 5 ] [3, 1, 2, 6, 4, 5 ] [3, 1, 2, 4, 6, 5 ] 1loop result = [3, 1, 2, 4, 5, 6 ] 이렇게하여 1loop가 끝난다. 2..
Computer Science
이진 탐색은 정렬된 데이터에서 특정한 값을 찾고자할 때 O(logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다. 2023.04.20 - [Data Structures & Algorithms] - 빅오 big-O 빅오 big-O 빅오 표기법 서로 간의 시간복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하게 일관된 언어로 설명하기 위한 수학적 언어이다. 빅오 표기법을 이용해 주어진 알고리즘 chaehun97.tistory.com O(logN)의 설명은 이전의 글에서 간략하게 써둔 것이 있으니 참고해보자.. 부족한 설명으로 이해가 되지 않을 수 있으니.. 다른 포스팅을 보는 것이 효율적일 수도 있다. 나중에 수정할 예정이니 참고만 해보자. 아마도 코드로 구현해보면 어떤 식으로 효율적..
빅오 표기법 서로 간의 시간복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하게 일관된 언어로 설명하기 위한 수학적 언어이다. 빅오 표기법을 이용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해 할 수 있다. 표기 : O(N) 빅오의 실행 속 O(1) → O(log N) → O(N) → O(N log N) → O(N^2) → O(N) → O(2^N) 아랫단계에 어떤 수를 곱하든 데이터가 커지다 보면 언젠가 윗 단계가 더 느려진다. 빅오의 N단계 빅오의 표현은 괄호 안에 있다. O(1)은 가장 빠른 알고리즘으로 분류한다. 데이터가 늘어나도 단계수는 증가하지 않는다. N이 얼마든 항상 상수단계에서만 필요하다. 빅오의 본질 데이터가 늘어날때 알고리즘의 성능이 어떻게 바뀌는지가 관건이다. 데이터..
읽기 자료구조내 특정위치를 찾아보는 것 컴퓨터는 딱 한 단계로 배열을 읽을 수 있으며, 프로그램에서 배열을 선언하면 연속된 빈 메모리 공간을 할당한다. 모든 메모리주소에 한번에 접근가능하며 배열을 할당할 때 어떤 메모리주소에서 시작하는지 기록해둔다. 배열은 기초적인 자료구조이지만 빠르게 읽을수 있는 강력한 자료구조이다. 검색 자료구조내 특정 값을 찾는 것 인덱스 제공 후 값을 반환하며 읽기에 비해 오래걸리며, 찾는 값이 가장 마지막 순서에 있다면 모든 값을 검색해야 한다. 배열에 값이 있다고 확신도 불가하다. N개로 이루어진 배열은 선형검색에 최대 N단계가 필요하다. 삽입 자료구조에 새로운 값을 추가하는 것 배열에 새 데이터를 삽입할 때 어디에 삽입하는가에 따라 효율성이 다르다. 배열에 맨끝에 삽입할때는..
