Java의 데이터 구조 및 알고리즘, Part 1 : 개요

Java 프로그래머는 데이터 구조를 사용하여 데이터를 저장하고 구성하고 알고리즘을 사용하여 해당 구조의 데이터를 조작합니다. 데이터 구조 및 알고리즘에 대해 더 많이 이해하고 이들이 함께 작동하는 방식을 더 많이 이해할수록 Java 프로그램의 효율성이 높아집니다.

이 튜토리얼은 데이터 구조와 알고리즘을 소개하는 짧은 시리즈를 시작합니다. 1 부에서는 데이터 구조가 무엇이며 데이터 구조가 분류되는 방식을 배웁니다. 또한 알고리즘이 무엇인지, 알고리즘이 어떻게 표현되는지, 시간 및 공간 복잡도 함수를 사용하여 유사한 알고리즘을 비교하는 방법도 배웁니다. 이러한 기본 사항을 익히면 Part 2에서 1 차원 배열을 사용한 검색 및 정렬에 대해 배울 준비가 된 것입니다.

데이터 구조 란 무엇입니까?

데이터 구조는 추상 데이터 유형 (ADT)을 기반으로하며 Wikipedia는 다음과 같이 정의합니다.

[A] 데이터 사용자의 관점에서 데이터 유형이 동작 (의미론)에 의해 정의되는 데이터 유형에 대한 수학적 모델, 특히 가능한 값,이 유형의 데이터에 대한 가능한 작업 및 동작 측면에서 이러한 작업의.

ADT는 해당 값의 메모리 표현이나 해당 작업이 구현되는 방식에 관심이 없습니다. 구현과 연결이 끊어진 데이터 유형 인 Java 인터페이스와 같습니다. 반대로 데이터 구조 는 Java 클래스가 인터페이스를 구현하는 방법과 유사하게 하나 이상의 ADT를 구체적으로 구현 한 것입니다.

ADT의 예로는 직원, 차량, 배열 및 목록이 있습니다. 공통 유형을 공유하는 정렬 된 요소 모음을 설명하는 List ADT (Sequence ADT라고도 함)를 고려하십시오. 이 컬렉션의 각 요소에는 고유 한 위치가 있으며 중복 요소가 허용됩니다. List ADT에서 지원하는 기본 작업은 다음과 같습니다.

  • 새롭고 빈 목록 만들기
  • 목록 끝에 값 추가
  • 목록에 값 삽입
  • 목록에서 값 삭제
  • 목록 반복
  • 목록 파괴

List ADT를 구현할 수있는 데이터 구조에는 고정 크기 및 동적 크기의 1 차원 배열과 단일 연결 목록이 포함됩니다. (2 부에서 배열을 소개하고 3 부에서 연결 목록을 소개합니다.)

데이터 구조 분류

단일 변수에서 배열 또는 여러 필드를 포함하는 개체의 연결된 목록에 이르기까지 다양한 종류의 데이터 구조가 있습니다. 모든 데이터 구조는 기본 또는 집계로 분류 될 수 있으며 일부는 컨테이너로 분류됩니다.

프리미티브 대 집합체

가장 단순한 종류의 데이터 구조는 단일 데이터 항목을 저장합니다. 예를 들어 부울 값을 저장하는 변수 또는 정수를 저장하는 변수가 있습니다. 이러한 데이터 구조를 기본 요소라고 합니다.

많은 데이터 구조가 여러 데이터 항목을 저장할 수 있습니다. 예를 들어 배열은 다양한 슬롯에 여러 데이터 항목을 저장할 수 있고 객체는 필드를 통해 여러 데이터 항목을 저장할 수 있습니다. 이러한 데이터 구조를 집계라고 합니다.

이 시리즈에서 살펴볼 모든 데이터 구조는 집계입니다.

컨테이너

데이터 항목이 저장되고 검색되는 모든 것이 데이터 구조로 간주 될 수 있습니다. 예를 들어 이전에 언급 한 직원, 차량, 배열 및 목록 ADT에서 파생 된 데이터 구조가 있습니다.

많은 데이터 구조가 다양한 엔터티를 설명하도록 설계되었습니다. 예를 들어 Employee클래스의 인스턴스는 다양한 직원을 설명하기 위해 존재하는 데이터 구조입니다. 대조적으로 일부 데이터 구조는 다른 데이터 구조에 대한 일반 저장 용기로 존재합니다. 예를 들어 배열은 기본 값이나 객체 참조를 저장할 수 있습니다. 이 후자의 데이터 구조 범주를 컨테이너라고 합니다.

집계 일뿐만 아니라이 시리즈에서 살펴볼 모든 데이터 구조는 컨테이너입니다.

Java 컬렉션의 데이터 구조 및 알고리즘

Java Collections Framework는 다양한 종류의 컨테이너 지향 데이터 구조 및 관련 알고리즘을 지원합니다. 이 시리즈는이 프레임 워크를 더 잘 이해하는 데 도움이 될 것입니다.

디자인 패턴 및 데이터 구조

대학생들에게 데이터 구조를 소개하기 위해 디자인 패턴을 사용하는 것이 일반적이되었습니다. Brown University 논문은 고품질 데이터 구조를 설계하는 데 유용한 몇 가지 설계 패턴을 조사합니다. 무엇보다도이 백서는 어댑터 패턴이 스택 및 대기열을 설계하는 데 유용하다는 것을 보여줍니다. 데모 코드는 목록 1에 나와 있습니다.

목록 1. 스택 및 큐에 어댑터 패턴 사용 (DequeStack.java)

public class DequeStack implements Stack { Deque D; // holds the elements of the stack public DequeStack() { D = new MyDeque(); } @Override public int size() { return D.size(); } @Override public boolean isEmpty() { return D.isEmpty(); } @Override public void push(Object obj) { D.insertLast(obj); } @Override public Object top() throws StackEmptyException { try { return D.lastElement(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } @Override public Object pop() throws StackEmptyException { try { return D.removeLast(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } }

목록 1 DequeStack은 어댑터 패턴을 보여주는 Brown University 논문의 클래스를 발췌 한 것 입니다. 참고 StackDeque스택 및 Deque와 ADT를을 설명하는 인터페이스입니다. MyDeque을 구현하는 클래스입니다 Deque.

인터페이스 메서드 재정의

목록 1의 기반이되는 원래의 코드에 소스 코드를 제공하지 않았다 Stack, Deque그리고 MyDeque. 명확성을 위해의 @Override모든 DequeStack비 생성자 메서드가 메서드를 재정의 한다는 것을 보여주는 주석을 도입했습니다 Stack.

DequeStackMyDeque구현할 수 있도록 적응합니다 Stack. 의 모든 DequeStack메서드는 Deque인터페이스의 메서드 에 대한 한 줄 호출 입니다. 그러나 Deque예외가 예외로 변환 되는 작은 주름이 Stack있습니다.

알고리즘이란?

역사적으로 수학적 계산 도구로 사용 된 알고리즘은 컴퓨터 과학, 특히 데이터 구조와 깊이 관련되어 있습니다. 알고리즘은 일정한 시간에 작업을 수행 지침의 순서입니다. 알고리즘의 특성은 다음과 같습니다.

  • 0 개 이상의 입력을받습니다.
  • 적어도 하나의 출력을 생성합니다.
  • 명확하고 모호하지 않은 지침으로 구성
  • 제한된 수의 단계 후에 종료됩니다.
  • 사람이 연필과 종이로 할 수있을만큼 기본

프로그램은 본질적으로 알고리즘적일 수 있지만 많은 프로그램은 외부 개입없이 종료되지 않습니다.

많은 코드 시퀀스가 ​​알고리즘으로 한정됩니다. 한 가지 예는 보고서를 인쇄하는 코드 시퀀스입니다. 더 유명한 것은 Euclid의 알고리즘이 수학적 최대 공약수를 계산하는 데 사용된다는 것입니다. 데이터 구조의 기본 작업 (예 : array slot에 값 저장 )이 알고리즘 인 경우도 있습니다. 이 시리즈에서는 대부분 이진 검색 및 행렬 곱셈 알고리즘과 같은 데이터 구조를 처리하는 데 사용되는 고급 알고리즘에 중점을 둘 것입니다.

순서도 및 의사 코드

알고리즘을 어떻게 표현합니까? 기본 알고리즘을 완전히 이해하기 전에 코드를 작성하면 버그가 발생할 수 있으므로 더 나은 대안은 무엇일까요? 두 가지 옵션은 플로차트와 의사 코드입니다.

순서도를 사용하여 알고리즘 표현

A flowchart is a visual representation of an algorithm's control flow. This representation illustrates statements that need to be executed, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. Figure 1 reveals the various symbols that flowcharts use to visualize algorithms.

Consider an algorithm that initializes a counter to 0, reads characters until a newline (\n) character is seen, increments the counter for each digit character that's been read, and prints the counter's value after the newline character has been read. The flowchart in Figure 2 illustrates this algorithm's control flow.

A flowchart's simplicity and its ability to present an algorithm's control flow visually (so that it's is easy to follow) are its major advantages. Flowcharts also have several disadvantages, however:

  • It's easy to introduce errors or inaccuracies into highly-detailed flowcharts because of the tedium associated with drawing them.
  • It takes time to position, label, and connect a flowchart's symbols, even using tools to speed up this process. This delay might slow your understanding of an algorithm.
  • Flowcharts belong to the structured programming era and aren't as useful in an object-oriented context. In contrast, the Unified Modeling Language (UML) is more appropriate for creating object-oriented visual representations.

Using pseudocode to represent algorithms

An alternative to flowcharts is pseudocode, which is a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, there are no hard-and-fast rules for writing pseudocode.

You should strive for consistency when writing pseudocode. Being consistent will make it much easier to translate the pseudocode into actual source code. For example, consider the following pseudocode representation of the previous counter-oriented flowchart:

 DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 DO READ ch IF ch GE '0' AND ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\n' PRINT count END

The pseudocode first presents a couple of DECLARE statements that introduce variables ch and count, initialized to default values. It then presents a DO loop that executes UNTILch contains \n (the newline character), at which point the loop ends and a PRINT statement outputs count's value.

For each loop iteration, READ causes a character to be read from the keyboard (or perhaps a file--in this case it doesn't matter what constitutes the underlying input source) and assigned to ch. If this character is a digit (one of 0 through 9), count is incremented by 1.

Choosing the right algorithm

The data structures and algorithms you use critically affect two factors in your applications:

  1. Memory usage (for data structures).
  2. CPU time (for algorithms that interact with those data structures).

It follows that you should be especially mindful of the algorithms and data structures you use for applications that will process lots of data. These include applications used for big data and the Internet of Things.

Balancing memory and CPU

When choosing a data structure or algorithm, you will sometimes discover an inverse relationship between memory usage and CPU time: the less memory a data structure uses, the more CPU time associated algorithms need to process the data structure's data items. Also, the more memory a data structure uses, the less CPU time associated algorithms will need to process the data items–leading to faster algorithm results.

As much as possible, you should strive to balance memory use with CPU time. You can simplify this task by analyzing algorithms to determine their efficiency. How well does one algorithm perform against another of similar nature? Answering this question will help you make good choices given a choice between multiple algorithms.

Measuring algorithm efficiency

Some algorithms perform better than others. For example, the Binary Search algorithm is almost always more efficient than the Linear Search algorithm–something you'll see for yourself in Part 2. You want to choose the most efficient algorithm for your application's needs, but that choice might not be as obvious as you would think.

For instance, what does it mean if the Selection Sort algorithm (introduced in Part 2) takes 0.4 seconds to sort 10,000 integers on a given machine? That benchmark is only valid for that particular machine, that particular implementation of the algorithm, and for the size of the input data.

As computer scientist, we use time complexity and space complexity to measure an algorithm's efficiency, distilling these into complexity functions to abstract implementation and runtime environment details. Complexity functions reveal the variance in an algorithm's time and space requirements based on the amount of input data:

  • A time-complexity function measures an algorithm's time complexity--meaning how long an algorithm takes to complete.
  • 공간 복잡성 함수 알고리즘의 측정 공간 복잡도 오버 헤드는 작업을 수행하는 알고리즘에 의해 요구되는 메모리의 양을 --meaning.

두 복잡도 함수는 입력 데이터의 양을 반영하는 입력 크기 ( n )를 기반으로합니다 . 배열 인쇄를 위해 다음 의사 코드를 고려하십시오.

 DECLARE INTEGER i, x[] = [ 10, 15, -1, 32 ] FOR i = 0 TO LENGTH(x) - 1 PRINT x[i] NEXT i END

시간 복잡도 및 시간 복잡도 함수

시간 복잡도 함수를 지정하여이 알고리즘의 시간 복잡도를 표현할 수 있습니다 . 여기서 (상수 승수)는 한 루프 반복을 완료하는 데 걸리는 시간을 나타내고 알고리즘의 설정 시간을 나타냅니다. 이 예에서 시간 복잡도는 선형입니다.t(n) = an+bab