IT관련정보/알고리즘(Algorithm) (3) 썸네일형 리스트형 3.탐색 알고리즘(Search Algorithm) 1.선형탐색(조건X) - O(n) def LinearSearch(arr,target): for i in range(len(arr)): if arr[i] == target: return i return 'Data Not Found' 1번째부터 n번째까지 순차적으로 비교해가면서 탐색하는 방법. 시간복잡도는 O(n)이다. 2.이진탐색(조건:정렬O) - O(logn) def BinarySearch(arr,target): buttom = 0 top = len(arr)-1 while buttom 2.정렬 알고리즘(Sorting Algorithm) ※일반정렬 1.버블정렬O(n²)버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다. def BubbleSort(arr): #버블정렬 알고리즘 for i in range(len(arr)): for j in range(1,len(arr)-i,1): if arr[j] < arr[j-1]: arr[j],arr[j-1] = arr[j-1],arr[j] return arr 2.선택정렬O(n²)선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. def SelectionSort(arr): #선택정렬 알고리즘 for i in range(len(arr)-1): key.. 1.공간복잡도&시간복잡도 ※공간복잡도&시간복잡도 1. 공간 복잡도(Space Complexity) : 알고리즘에 사용되는 메모리 공간의 총량 예를 들어, 크기가 N인 배열을 만든다고 가정하면 공간 복잡도가 O(N)이 되고 NxN인 배열을 만들면 O(N²)이 됩니다. 함수의 재귀적인 호출의 경우 스택 공간도 고려해야 합니다. !!인자로 받은 데이터는 제외, 함수내에서 사용할경우 포함 1) def Num1(a,b): --공간복잡도 0 return a+b 2) def Num2(arr,n): --공간복잡도 arr+(n,i,result) => n+3 result = 0 for i in range(n): result += arr[i] return result 3) 재귀함수(recursion)는 깊이 * (변수갯수+복귀주소(1)) 로 공간복.. 이전 1 다음
