이산수학 8. 시간 복잡도, 계산 복잡도, 알고리즘 복잡도(Time Complexity, Complexity of Algorithms)

안녕하세요 블레이즈입니다. 

 

첫 번째 문제입니다. 첫 번째 문제는 시간복잡도 문제의 증명이네요.

n log n 가 O(log n!) 임을 증명하기.

 

두 번째 문제입니다.  두 번째 문제는 알고리즘 복잡도 문제입니다.

알고리즘을 보고 이 알고리즘의 계산복잡도가 어느 정도인지 확인해보는 것입니다. 

 

 

while 문의 조건을 확인하기 위한 비교는 제외하고 다음의 알고리즘에서 수행된 더하기/곱하기 연산의 횟수를 big-O 로 나타내기.

 

i := 1

t := 0 

while i ≤ n

    t := t + i

    i := 2i

 

 

감사합니다.

블레이즈 테크 노트

Blaze Tech Note