def CalcSum(n):
sum = 0
for i in range(1, n+1)
sum += 1
return sum
# 1+n*2 = 2n+1
def CalcSum(n):
return n(n+1)/2
시간복잡도 = 빅-오(O) 표기법
Big-Oh Notation
시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
계수(Coeficient)는 생략
예)
O(3n+2) = O(3n) = O(n) #최고차항을 선택하고 계수를 제거
배열
일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
배열의 필요성
프로그램 내에서 여러 개의 변수가 필요할 때, 모두 독립적 변수명을 이용하여 자료에 접근하는 것이 비효율적일 수 있음
배열을 사용하면 하나의 선언을 통하여 둘 이상의 변수를 선언할 수 있음
다수의 변수로는 하기 힘든 작업도 배열을 사용해 쉽게 수행할 수도 있음
1차원 배열의 선언
별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때 생성
배열의 길이는 선언시 정해 놓는 것이 좋음 ex) arr = [0] * 100
정렬
2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 혹은 그 반대의 순서대로 재배열하는 것
정렬방식의 종류
버블 Bubble
카운팅 Counting
선택 Selection
퀵 Quick
삽입 Insertion
병합 Merge
버블정렬
인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
정렬과정
첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고하여 버블 정렬이라고 한다.
시간복잡도
O(n ** 2)
예시
numList = [55, 7, 78, 12, 42]
for i in range(len(numList)-1, 0, -1):
for j in range(i):
if numList[j] > numList[j+1]:
numList[j], numList[j+1] = numList[j+1], numList[j]
# 버블정렬
