Big-O example

# 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