Algorithms6 알고리즘 개념 7. 병합정렬 Merge sort 개념 두개로 나누고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결한다. 두 개로 나눈 리스트를 재귀적으로 합병정렬을 이용해 정렬하고, 나중에 다시 합친다. 글로는 잘 이해가 안가니까 사진 참고. 분할 -> 정복(정렬) -> 병합 이때 걸리는 시간? O(n log n) 의 시간복잡도를 갖는다. 장점? - 데이터 특성과 상관없이 같은 양이면 정렬시간은 비슷하다. - 각각의 레코드를 Linked list 로 구성하면, 데이터 이동은 엄청 작아진다. 따라서 크기가 큰 것을 정렬할때 연결리스트를 사용한다면 매우 효율적이다. 단점? - 레코드가 Array면 임시배열이 필요하고, in-place sorting이 아니다 - 크기가 크면 이동횟수가 많아서 비효율적이다. ** Stable sort, Unstable.. 2020. 11. 10. 알고리즘 개념 6. 삽입정렬 (Insertion sort) 개념? - 자신보다 그 앞의 원소가 큰지, 작은지를 판단하여 자신의 위치를 찾아 삽입하는 정렬 - 오름차순,내림차순 - 자기자신이 n번째에 있으면 첫번째원소부터 n까지 비교 시간복잡도: O(n^2) -특정한 경우에 빠른 속도가 나지만(정렬이 되어있다고 가정), 배열이 길어지면 효율이 떨어진다. 예시 9 4 6 2 1 5 단계별 출력 9 4 9 4 6 9 2 4 6 9 1 2 4 6 9 1 2 4 5 6 9 def insert_sort(x): for i in range(1, len(x)): j = i - 1 key = x[i] while x[j] > key and j >= 0: x[j+1] = x[j] j = j - 1 x[j+1] = key return x python 코드 포인트 arr[i - 1], .. 2020. 11. 9. 알고리즘 개념 4. 선택정렬 Selection sort - 제자리 정렬 알고리즘 - 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 순서 (1) 주어진 리스트에서 최솟값을 찾는다 (2) 그 최솟값을 맨 앞의 값과 교체한다. (pass) (3) 맨 앞 위치를 빼고 나머지 리스트를 같은 방법으로 계속 정렬한다. 걸리는 시간은? n개의 리스트가 있다고 한다면 Θ(n2)만큼 시간이 걸린다. * for loops 2개로 이루어짐 -> 첫번째 루프횟수 : (n-1) 두번째도 (n-1) * 값 교환 횟수 = 3(n-1) 장점? 자료의 이동횟수가 미리 정해져 있다 단점? 안정성을 만족하지 않고, 값이 같은 속성이 있는 경우 상대적 위치가 변경될 수 있다. python example def selectionSort(x): length = len(x) for i.. 2020. 11. 3. 알고리즘 개념 3. 점화식 Recurrence relation 점화식이란? - 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 (ex) 등차수열, 팩토리얼 점근적 분석 방법의 종류? (1) 반복 대치 : 더 작은 문제에 대한 함수로 반복해서 대치함 (2) 추정 후 증명 : 식의 모양을 보고 점근적 복잡도를 추정한 다음, 그 것의 옳음을 수학적으로 귀납적 증명 (3) 마스터 정리 : 특정 형식에 맞는 점화식의 복잡도를 계산이나 증명없이 알수있는 정리 2020. 11. 2. 알고리즘 개념 2. 점근적 표기 (Asymptotic notation) 점근적 분석? - 주어진 문제에 대한 여러 알고리즘이 있을때, 효율성을 비교하기위한 분석 점근적 증가율? - 변수크기가 충분히 크면 변수증가에 따라 함수가 증가하는 비율(함수를 비교할 때, 상수나 작은 인풋은 무시) 점근적 표기법? (1) O-표기법 - 알고리즘이 아무리 안좋아도, 비교하는 함수와 같거나, 그거보다 좋다 - 점근적 상한선(Asymptotic upper bound)만 알고있다면 이 표기법 사용 - (ex)이 알고리즘은 적어도 00정도의 성능이 나온다 할때 사용 - (2) 𝛺-표기법 - 알고리즘이 아무리 좋아도, 기존 비교하는 함수 이하이다. - 점근적 하한선(Asymptotic lower bound) - O-표기법의 반대개념 - (3) 𝛩-표기법 - 알고리즘이 아무리 좋아도,나빠도, 기존 .. 2020. 10. 28. 알고리즘 개념 1. 재귀(자기호출)와 귀납법 알고리즘의 정의: 어떤 작업을 수행하기 위한 과정을 기술한 것 (입력부터 출력까지) 재귀(Recursion, 자기호출) : 어떤 사건이 자기자신을 포함한 상태로, 다시 자기자신을 사용하여 정의 될 때. : 수학적 관점에서 재귀 함수로 많음(ex.factorial) 알고리즘 관점에서 "재귀"는? : 어떤 작업을 수행하면서, 자기자신과 같지만 크기가 다른 문제의 관계를 파악하여 문제를 해결해나가는 방식을 의미함 : 자기자신보다 작은 문제를 자기호출한다는 것은, 자신보다 작은 문제에서는 알고리즘이 정상임을 가정 귀납적 사고? : 속성이 같지만 크기가 다른 문제의 관계를 파악하는 것 기타 지식 : 개념 자체는 반복문과 비슷. : 재귀는 지속적으로 함수를 호출하여 계속 스택을 생성한다. 메모리 낭비 주의. (스택.. 2020. 10. 27. 이전 1 다음
