알고리즘(개념, 분석, 원시연산

by

알고리즘 기본 개념

알고리즘은 지정된 시간 내에 문제를 해결하기 위한 일련의 단계입니다.

“0개 이상의 입력이 주어지면 1 이상의 값을 도출하는 방법 또는 프로세스”

  • 항해 – 루트 찾기 알고리즘
  • MP3/4 파일 전송 -압축 알고리즘
  • 태양 전지 – 최적화 알고리즘
  • 2D/3D 모델 이미지 생성 -렌더링 알고리즘

그렇다면 어떻게 “좋은” 알고리즘을 만들 수 있습니까?

'추천 관련글,

지금까지 좋은 알고리즘뭐야?

알고리즘 분석

알고리즘 분석컴퓨터 프로그램이다 성능 및 리소스 소비에 대한 이론적 연구이다.

  • 첫 번째 초점: 런타임(시간 복잡도)
  • 두 번째 초점: 메모리 활용(공간 복잡성)

지속입력의 크기와 인스턴스, 사용된 알고리즘 및 실행된 입력입니다.

소프트웨어 및 하드웨어 환경~에 달려있다


알고리즘(개념, 분석, 원시연산 1
겁쟁이. 1. 더 빠른 컴퓨터 런타임과 더 느린 컴퓨터 런타임 비교

알고리즘을 분석하기 위해 실행 시간을 경험적으로 관찰하는 실험을 수행하기도 합니다.


이렇게 하려면 샘플 입력 웰을 선택하고 정확한 수의 테스트 완료해야 합니다(그러면 분석에 대한 통계적 확실성이 있음).

실험분석 시 주의사항

  1. 실험 제한된 일련의 테스트 입력에서 수행됩니다.

  2. 모든 테스트는 동일합니다.

    하드웨어와 소프트웨어로 완성당신은해야합니다.

  3. 알고리즘을 구현하고 실행해야 합니다.

이론적 분석

이론적 분석은 실험적 분석보다 장점이 있습니다.

  1. 가능한 모든 입력을 고려할 수 있습니다.

  2. 하드웨어/소프트웨어 환경에 독립적인 둘 이상의 알고리즘의 효율성 비교
  3. 연산(의사 코드)여기에는 다음에 대한 높은 수준의 설명을 연구하는 것이 포함됩니다.

공식적인 이론적 분석에는 다음이 필요합니다.

  • 알고리즘을 설명하기 위해 언어
  • 알고리즘이 실행 중입니다 계산 모델
  • 성능 측정을 위해 측정 기준
  • 성능 성격 묘사어떻게 하나

대문자

  • 의사 코드는 알고리즘에 대한 고급 설명 언어입니다.

  • 의사 코드는 알고리즘에 대한 보다 체계적인 설명을 제공합니다.

  • 알고리즘의 고급 분석을 통해 실행 시간(및 메모리 요구 사항)을 결정할 수 있습니다.

  • 의사 코드는 자연어와 고급 프로그래밍 언어(예: Java, C 등)의 혼합입니다.

  • 데이터 구조 또는 알고리즘의 일반적인 구현을 설명합니다.

  • 의사 코드에는 표현식, 선언, 변수 초기화 및 할당, 조건부, 루프, 배열, 메서드 호출 등이 포함됩니다.


알고리즘(개념, 분석, 원시연산 2
겁쟁이. 2. 물 코드

그림 2에서 분 < ㅡ A (0) min이라는 변수에 A(0)을 할당하는 것을 의미합니다.

알고리즘 분석은 기본 작업의 수를 세는 것으로 시작됩니다.

기본 작업은 다음을 의미합니다.

1. 변수에 값 할당
2. 함수 호출
3. 산술 연산 수행
4. 두 값 비교
5. 배열의 인덱싱
6. 개체 참조
7. 반환 함수 값

랜덤 액세스 머신

컴퓨터에서 간단한 계산 램.~을 통해 계산 모델원인

계산 모델은 컴퓨터가 일정한 시간 동안 수행할 수 있는 작업, 알고리즘이 수행할 수 있는 작업 및 소요 시간을 설명합니다.

비용(시간)을 결정합니다.

하다.

즉, 각 작업에 소요되는 시간

따라서 계산 모델에 익숙하다면 알고리즘 생성에 대한 생각을 구조화할 수 있습니다.

전산 모델에는 두 가지 주요 유형이 있습니다(랜덤 액세스 머신(RAM) 및 포인터 머신) 각기 다른


알고리즘(개념, 분석, 원시연산 3
겁쟁이. 3. A~G 실행 결과

  • 일부 입력은 다른 입력보다 빠르게 수행될 수 있습니다.

  • 평균 사례 복잡도동일한 크기의 모든 입력에 대해 평평합니다.

    평균 실행 시간수단
  • 최악의 경우 복잡성같은 크기의 용어 모든 입력이 차지하는 최대값보다 나타내다

“보통 우리는 주로 최악의 복잡성에 관심이 있습니다.

”

기본 작업 계산


알고리즘(개념, 분석, 원시연산 4
겁쟁이. 4. 물 규제의 예

만약에 겁쟁이. 4 동일한 대문자 코드의 원시 연산에 대한 최상의 경우와 최악의 경우를 계산하면 위의 대문자 코드에서 살펴본 원시 연산 7개의 내용을 짐작할 수 있습니다.

더보기


알고리즘(개념, 분석, 원시연산 5
겁쟁이. 5. 답변

1. 어레이 액세스 하나 + 변수에 값 할당 하나 = 2

2. 변수 j에 값 할당 하나 + 변수 비교 N = 1 + n (변수 비교는 for문의 반복으로 인한 것이다.

n번)

3. 배열 접근법 n-1 + 변수 비교 n-1 = 2(n-1) (배열 액세스는 n-1for 문 안에 있기 때문에)

4. 배열 접근법 n-1 + 변수 할당 n-1 = 2(n-1)

5. 반환 함수 값 하나

* 이 주문만 실행된다면 총 5n의 기본 케이스이며,

for 문에 i++를 포함하면 7n-2가 최악의 경우가 됩니다.

재귀 알고리즘이란 무엇입니까?

재귀에는 더 작은 하위 문제를 해결하기 위해 자신을 호출하는 절차가 포함됩니다.

이러한 더 작은 하위 문제는 더 큰 문제에 대한 솔루션에 도달하기 위해 어떤 방식으로 결합될 수 있습니다.

재귀 알고리즘은 종종 비재귀 버전보다 작성하기 쉽지만 피해야 할 이유가 종종 있습니다.


예를 들어 Fibonacci(n)을 계산하려면 Fibonacci(n-1)그리고 피보나치(n-2)계산해야합니다.

그런 다음 이 두 함수 호출은 피보나치입니다.

(n-3)그리고 피보나치(n-4) 등을 계산해야 합니다.

이러한 작업의 반복은 전체 실행 시간이 크게 증가하고 메모리 사용량도 증가하여 성능 저하아마도


알고리즘(개념, 분석, 원시연산 6
겁쟁이. 6. 피보나치 알고리즘의 예

참조