Algorithms(알고리즘)

Algorithms

---

Definition

Applying a technique to a problem results in a step-by-step procedure for solving the problem. This step-by-step procedure is called an algorithm for the problem.

 

Objectives

The purpose of studying these techniques and their applications is so that, when confronted with a new problem, you have a repertoire of techniques to consider as possible ways to solve the problem. Technique is not a programming style or a programming language, but the approach or methodology used to solve a problem. In addition, we will be concerned not only with determining whether a problem can be solved using a given technique but also with analyzing how efficient the resulting algorithm is in terms of time and storage.

 

👉 알고리즘이란 문제를 해결하기 위한 일련의 절차적인 과정이다. 

알고리즘 학습의 목적은 새로운 문제에 직면했을 때, 문제를 해결할 수 있는 방법으로 고려해야 할 기술의 레퍼토리를 가지기 위함이다. 여기서 기술이란 프로그래밍 스타일이나 프로그래밍 언어가 아니라 문제를 해결하는 데 사용되는 접근 방식이나 방법론을 의미한다.

주어진 기술을 사용하여 문제해결의 가능여부를 결정해야 하며, 알고리즘의 결과가 시간 및 스토리지면에서 얼마나 효율적인지 분석해야 한다.

 

Reference Books

Foundations of Algorithms 4th Edition by Richard Neapolitan (Author)

 

 

 

The Importance of Developing Efficient Algorithms

---

Regardless of how fast computers become or how cheap memory gets, efficiency will remain an important consideration. Next we show why this is so by comparing two algorithms for the same problem.

Array Size	Number of Comparisons by Sequential Search	Number of Comparisons by Binary Search
128	128	8
1,024	1,024	11
1,048,576	1,048,576	21
4,294,967,296	4,294,967,296	33

 

Binary Search does only 33 comparisons, whereas Sequential Search compares x with all 4 billion items. Even if the computer was capable of completing one pass through the while loop in a nanosecond, Sequential Search would take 4 seconds to determination almost instantaneously. This difference would be significant in an online application or if we needed to search for many items.

 

👉 컴퓨터가 얼마나 빨라지거나 메모리가 얼마나 저렴한지에 관계없이 알고리즘의 효율성은 여전히 중요한 고려사항이다.

목푯값을 탐색하는 데 있어 Binary Search는 33번의 비교연산이면 충분하지만, Sequential Search는 40억개의 배열항목과 모두 비교해야 한다. 이 차이는 온라인 응용프로그램이나 많은 항목을 검색해야 할 때 중대한 사항이다.