The RAM Model of Computation - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:25:35Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:25 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#알고리즘 분석\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#알고리즘 분석\|알고리즘 설계와 분석]]

2025년 9월 5일 (금) 22:48에 Pinkgo님의 편집

2025-09-05T22:48:56Z

← 이전 판		2025년 9월 5일 (금) 22:48 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
			상위 문서: [[알고리즘 설계와 분석#알고리즘 분석\|알고리즘 설계와 분석]]

	==개요==		==개요==
	기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다.		기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다.

2025년 9월 5일 (금) 16:37에 Pinkgo님의 편집

2025-09-05T16:37:01Z

← 이전 판		2025년 9월 5일 (금) 16:37 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]

	==개요==		==개요==
	기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다.		기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다.

2025년 9월 5일 (금) 16:27에 Pinkgo님의 편집

2025-09-05T16:27:28Z

← 이전 판		2025년 9월 5일 (금) 16:27 판
8번째 줄:		8번째 줄:
	* 각 메모리 접근은 정확히 한 시간 단계(time step)를 소요한다.		* 각 메모리 접근은 정확히 한 시간 단계(time step)를 소요한다.
	RAM 모델에서 실행 시간은 주어진 문제 인스턴스에서 알고리즘이 수행하는 단계 수를 통해 측정한다. 이때 RAM이 초당 일정한 수의 단계를 수행한다고 가정한다면, 이 연산 계수는 실제 실행 시간으로 자연스럽게 변환된다. RAM은 컴퓨터가 수행하는 방식을 단순화한 모델이다. 이는 너무나 단순화한 나머지 실제로 컴퓨터가 동작하는 방식과는 차이가 있지만, RAM은 실제 컴퓨터에서 알고리즘이 어떻게 성능을 낼지를 이해하는 데 훌륭한 모델이다.		RAM 모델에서 실행 시간은 주어진 문제 인스턴스에서 알고리즘이 수행하는 단계 수를 통해 측정한다. 이때 RAM이 초당 일정한 수의 단계를 수행한다고 가정한다면, 이 연산 계수는 실제 실행 시간으로 자연스럽게 변환된다. RAM은 컴퓨터가 수행하는 방식을 단순화한 모델이다. 이는 너무나 단순화한 나머지 실제로 컴퓨터가 동작하는 방식과는 차이가 있지만, RAM은 실제 컴퓨터에서 알고리즘이 어떻게 성능을 낼지를 이해하는 데 훌륭한 모델이다.

			==Best/Worst/Average-Case Complexity==
			RAM 모델을 사용하면 주어진 입력 인스턴스에 대해 알고리즘을 실행하여 해당 알고리즘이 수행하는 단계의 수를 셀 수 있다. 그러나 일반적으로 어떤 알고리즘이 좋은지 나쁜지를 판단하기 위해서는, 가능한 모든 인스턴스에 대해 그것이 어떻게 동작하는지를 알아야 한다.

			최선, 최악, 평균 경우 복잡도(Best/Worst/Average-Case Complexity)의 개념을 이해하기 위해서 해당 알고리즘에 입력될 수 있는 가능한 모든 데이터 인스턴스에 대해 알고리즘을 실행한다고 가정하자. 예를 들어 정렬 문제의 경우, 가능한 입력 인스턴스 집합은 모든 가능한 n<ref>n은 자연수이다.</ref>개의 키의 배열이다. 이때 각 입력 인스턴스는 figure 1에 나타난 좌표평면 위의 한 점으로 나타내어 진다. 해당 좌표평면에서 x축은 입력 문제의 인스턴스 크기를, y축은 해당 인스턴스에서 알고리즘이 수행한 단계의 수를 나타낸다. 이때 우리는 해당 좌표평면에서 세 가지 흥미로운 함수를 정의할 수 있다.
			# Worst-Case Complexity는 크기 n의 어떤 인스턴스에 대하여 수행된 단계 수의 최댓값으로 정의되는 함수이다. 이는 평면에서 가장 높은 점을 지나는 곡선에 해당된다.
			# Best-Case Complexity는 크기 n의 어떤 인스턴스에 대하여 수행된 단계 수의 최솟값으로 정의되는 함수이다. 이는 평면에서 가장 낮은 점을 지나는 곡선에 해당된다.
			# Worst-Case Complexity<ref>기대 시간(expected time)이라고도 한다.</ref>는 크기 n의 모든 인스턴스에 대해 실행된 단계 수의 평균으로 정의되는 함수이다.
			일반적으로는 이 세가지 측정치 중 Worst-Case Complexity가 가장 유용하다.

	==각주==		==각주==

Pinkgo: 새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 ==개요== 기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다. * 각각의 단순 연산(+, , –, =, if, call)은 정확히 한 시간 단계(time step)를 소요한다. 반복문과 서브루틴은 단순 연산으로 간주되지 않는다. *...

2025-09-05T16:03:49Z

새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 ==개요== 기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다. * 각각의 단순 연산(+, *, –, =, if, call)은 정확히 한 시간 단계(time step)를 소요한다. * 반복문과 서브루틴은 단순 연산으로 간주되지 않는다. *...

새 문서

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]

==개요==
기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다.
* 각각의 단순 연산(+, *, –, =, if, call)은 정확히 한 시간 단계(time step)를 소요한다.
* 반복문과 서브루틴은 단순 연산으로 간주되지 않는다.
* 각 메모리 접근은 정확히 한 시간 단계(time step)를 소요한다.
RAM 모델에서 실행 시간은 주어진 문제 인스턴스에서 알고리즘이 수행하는 단계 수를 통해 측정한다. 이때 RAM이 초당 일정한 수의 단계를 수행한다고 가정한다면, 이 연산 계수는 실제 실행 시간으로 자연스럽게 변환된다. RAM은 컴퓨터가 수행하는 방식을 단순화한 모델이다. 이는 너무나 단순화한 나머지 실제로 컴퓨터가 동작하는 방식과는 차이가 있지만, RAM은 실제 컴퓨터에서 알고리즘이 어떻게 성능을 낼지를 이해하는 데 훌륭한 모델이다.

==각주==