Big Ω 란 Definition: (Asymptotic Lower Bound) N보다 큰 모든 부분에서 f(n) 에 어떤 양의 실수 c를 곱한 값이 g(n) 보다 작은 값으로 존재하는 것. N보다 작은 부분은 상관없다. g(n) ∈ Ω(f(n) g(n) ≥ c × f(n) g(n) ∈ Ω(f(n) 의 의미 N보다 작은 부분에서는 cf(n)이 g(n)보다 크지만, 결국에는 N 보다 큰 모든 부분에서 cf(n) 보다 커져서 cf(n) 위에 머무르게 된다. g(n)이 알고리즘의 시간 복잡도라면 결국 알고리즘의 실행 시간은 최소한 f(n) 보다는 크거나 같도록 갖게 된다. g(n)은 f(n)보다 빠르게 실행될 수 없다. n^2+10n∈Ο(n^2) ? c =1 , N=0 이면 모든 실수 n≥ 0에 대하여 n^2..
Representatvie Order Fuctions Θ(lg n) (로그 시간 복잡도): 이 함수는 로그 시간 복잡도를 나타내고 주로 이진 검색과 같이 큰 데이터 집합에서 효율적인 검색 알고리즘에 적용된다 . 시간이 데이터의 크기에 대해 로그 성장한다. Θ(n) (선형 시간 복잡도): 이 함수는 선형 시간 복잡도를 나타내고 시간이 입력 크기에 비례하여 선형적으로 증가한다. 예를 들어, 리스트의 모든 요소를 한 번 씩 훑는 경우에 해당한다. Θ(n lg n) (선형로그 시간 복잡도): 이 함수는 선형로그 시간 복잡도를 나타낸다. 주로 효율적인 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)과 관련이 있다. Θ(n^2) (제곱 시간 복잡도): 이 함수는 제곱 시간 복잡도를 ..
시간 복잡도 분석 입력 크기의 각 값에 대해 기본 연산( 비교 Comparisons, 할당 assignments ,etc )을 몇 번 수행하는지가 결정한다. cpu 나 os 프로그래밍 언어 등의 요소에 독립적으로 판단되어야 한다. Comparisons, assignments input size 예시로는 배열의 요소의 개수나 리스트의 길이 행렬의 행과 열, 그래프 간선과 모소리 개수가 있다. Every-case analysis 문제와 종류와 상관있는 분석으로 예를 들어1부터 n까지 더하는 알고리즘 인 경우 배열의 크기가 만 결정 되어지면 배열의 값에 상관없이 항상 n개의 연산이 필요하다.' Worst-case analysis 알고리즘의 수행 시간이 최악의 경우에 얼마나 나쁠 수 있는지에 중점을 둔다. 예를..
피보나치 수열(Fibonacci sequence)이란 ? 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 처럼 나열 되는 수열으로 규칙은 다음과 같다 첫 번째 항: F(0) = 0, 두 번째 항: F(1) = 1 , 나머지 항: F(n) = F(n-1) + F(n-2) (단, n은 2 이상의 정수) 즉, 피보나치 수열은 첫 번째 항과 두 번째 항이 각각 0과 1이며, 이후의 모든 항은 바로 앞의 두 항을 더한 값이다. 재귀로 나타낸 피포나치 코드 피보나치의 재귀적 솔루션으로 n번째 숫자를 구할때 필요한 계산 횟수는 ? 이다. 피보나치 수열의 5번쨰 수를 재귀 알고리즘의 구하는 과정을 나타내면 다음과 같다. 재귀 호출의 깊이를 D(n)으로 표시하면 D(n)은 D(n-1) + D(n..
Sequential Search (순차 탐색) 리스트 S ( n = 리스트 S의 사이즈) 에서 x가 S의 몇번째 위치에 존재 하는지 확인하는 문제 Inputs (parameters) : 양의 정수 n, 배열 S , indexed from 1 to n Output S에서 x의 위치, S에 존재 하지 않으면 0 Algorithm : 리스트 S의 첫 번째 리스트 요소부터 시작하여, S의 요소들을 x를 찾았거나, S의 모든 요소들을 다 비교했을 때까지 x와 비교한다. 이 과정에서 x를 찾았다면 답은 yes이고, 없다면 답은 0으로 둔다. S에서 x의 위치(x가 S에 존재한다고 가정)를 찾기 위해 비교한 횟수는 S에서 x의 위치에 달려있다 최악의 경우 n 번 (리스트 s의 사이즈) 비교 해야 한다...
Problem 리스트 S ( n = 리스트 S의 사이즈) 에서 x가 존재 하는지 유무를 확인하는 문제 x가 리스트 S에 존재하면 답은 yes 이고 존재하지 않으면 답은 no이다. Problem instance Problem instance는 컴퓨터 과학과 이산수학에서 사용되는 용어로, 특정 문제의 구체적인 입력 데이터나 예제를 나타내는 것을 의미한다. 문제의 정의나 설명은 하나의 추상적인 개념일 수 있지만, 실제로 문제를 해결하려면 구체적인 값을 사용 해야 한다 리스트 S ( n = 리스트 S의 사이즈) 에서 x가 존재 하는지 유무를 확인하는 문제의 Problem instance 표현 - S = [10,7,11,5,13,8] , n = 6 , x = 8 - S = [10,7,11,5,13,8] (사이즈 ..
