배열의 원소의 총합 계산하기

n = [13,6,9,8,12]

def total(array, sum=0):
    #array의 비교할 것이 남아있지 않다면,
    if not array:                   
        #sum을 넘기면서 프로그램을 종료한다.
        return sum                  
    #sum에 첫번째 원소를 더한다.
    sum += array[0]                 
    #이미 더한 원소를 빼기위해서 0번째 원소를 뺀 배열과 더해져있는 sum을 리턴한다.
    return total(array[1:], sum)

print(total(n))

해당 함수의 시간복잡도는 배열의 길이의 비례만큼 실행되기 때문에 시간복잡도는 $O(n)$이다.

n = [13,6,9,8,12]

def min(array, com):
    #array의 비교할 것이 남아있지 않다면,
    if not array: 
        #com을 넘기면서 프로그램을 종료한다.                              
        return com                              
    #배열의 첫번째를 now로 선언.
    now = array[0]                              
    #now가 com보다 작다면,
    if now < com:                               
        #배열의 첫번째수가 비교하는 수보다 작으면, now를 com로 대체한다.
        return min(array[1:], now)              
    #now가 com보다 작지 않다면,
    else:                                       
        #배열의 첫번째가 비교하는 수보다 작지 않다면, com을 유지한다.
        return min(array[1:], com)              

def selection_sort(array, count=0):
    #array의 길이 만큼, count가 진행되었다면,
    if count == len(array):                     
        #array를 리턴.
        return array                            

    #min함수를 사용하여서 배열의 가장 최솟값을 찾아 mini에 저장
    mini = min(array[count:], array[count])     
    #최솟값 mini의 index번호를 찾는다.
    index = array.index(mini)                  
    array[index] = array[count]                 
    #단계(count)의 맞게 찾은 최솟값을 대상의 array와 위치를 바꾼다.
    array[count] = mini                         
    #다음 최소값을 찾기 위해서, count를 1증가 시켜 다음 단계를 진행.
    count += 1                                  
    return selection_sort(array, count)         

print(selection_sort(n))

데이터의 개수가 n개라고 했을 때,
첫 번째 회전에서의 비교횟수 1 ~ (n-1) => n-1
두 번째 회전에서의 비교횟수 2 ~ (n-1) => n-2 … (n-1) + (n-2) + … + 2 + 1
=> n(n-1)/2 이므로 선택 정렬의 시간복잡도는 $O(n^2)$이다.