상세 컨텐츠

본문 제목

Big-O example

Python

by techbard 2016. 5. 4. 11:14

본문

반응형

# Big-O Examples


# O(1) Constant


""" 입력이 무한히 많아도 1회 실행한다. """

def func_constant(values):

print(values[0])


lst = [1, 2, 3, 4, 5, 6]


func_constant(lst)


# O(n) Linear


""" 입력 전체를 직선적으로 순회하면서 실행한다. """

def func_lin(lst):

for val in lst:

print(val)


func_lin(lst)


# O(n^2) Quadratic


""" 입력이 제곱수로 늘어나면서 실행한다. """

def func_quad(lst):

for item_1 in lst:

for item_2 in lst:

print(item_1, item_2)


func_quad(lst)


# complex Big O


def comp(lst):

print(lst[0]) # O(1)


midpoint = len(lst) // 2 # O(n/2)


for val in lst[:midpoint]:

print(val)


for x in range(10): # O(10)

print('hello world')


# => O(1 + n/2 + 10)


lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


comp(lst)


# 실행 효율성 - 내장함수가 효율이 좋다.


import timeit


def method1():

l = []

for n in range(10000):

l = l + [n]


def method2():

l = []

for n in range(10000):

l.append(n)


def method3():

l = [n for n in range(10000)]


def method4():

l = list(range(10000))


t = timeit.Timer(method1).timeit(number=10)

print(t)

t = timeit.Timer(method2).timeit(number=10)

print(t)

t = timeit.Timer(method3).timeit(number=10)

print(t)

t = timeit.Timer(method4).timeit(number=10)

print(t)


# 결과

1.208771167255275

0.010398140601889372

0.005334299254429631

0.0023302846448731707


반응형

관련글 더보기

댓글 영역