[질문]알고리즘이 얼마나 효율적인지 어떻게 증명하죠?

OpenSnake의 이미지

A[0,1,2,3,4..........n] 의 배열있다면 여기서 가장 큰수을 찾는 알고리즘을 제작한다고
한다면요..

그걸 어떻게 증명하죠??

수학으로 증명을 하기도 하던데요...수학에서는 "몇번 비교했나"이걸로 증명하더군요.
하지만 제 생각에는 "몇번비교"말고도 다른요소도 첨가시켜야 하는거 아닌가요??

어떤 알고리즘이 있으면 이게 얼마나 효율적인지 시간으로 알수는 없나요?

ckebabo의 이미지

먼저 단위연산이 무엇인지를 파악한 후 이것들이 입력의 크기에 따라 어떻게 비례하여 증가하는 지를 따져보게 됩니다...
이를 Time Complexity라고 하는데...보통 Big-O 표기(또는 Theta)로 많이 표현하죠...

위의 예에서처럼 배열에서 최대값찾는 경우엔 단위연산이 비교하는 작업이 될 수가 있는 거죠...

Big-O의 정의에 따라 차수가 높을수록 '일반적으로' 시간이 더 많이 걸리겠구나 하고 생각할 수 있는 것이죠...하지만 상수들(계수와 같은)이 숨겨져 있기에 특정 threshold를 경계로 그런 생각이 역전되기도 해요...

허접한 댓글 죄송...
알고리즘관련 책의 앞부분이나 계산이론책들을 보면...좀 더 잘 아실 수 있을 거예요...

bluelenz의 이미지

알고리즘 수업을 들으면 그런게 나오는데요

언급하신 탐색문제는
주된 연산이 비교연산이고 그 비교연산이 일정횟수 반복되니까
비교연산의 비용을 상수로 생각하고
비교연산이 얼마나 반복되는지를 따지는 겁니다
또 다른 연산이 반복된다면 그것도 생각해야겠지요

이게 input의 조건에 따라서도 달라질 수 있는데
array를 적어 놓으셨으니
index를 가지고 상수시간만에 값에 접근할 수 있는데
linked list 였다면 그 값에 접근하는데도 비용이 필요하겠고
그렇다면 그 비용도 따져야겠지요

적어 놓으신 것 처럼 순차적인 값이라면
(사실 그렇다면 search할 필요 없겠죠;)
모든 수를 비교할 필요가 없지만

이게 임의의 값들의 집합이라면
모든 값들은 최소한 한번은 비교해봐야
최대값이 아니라는 걸 확인할 수 있으니까
n 개의 elements 중에 최대값을 찾으려면
n-1 번의 비교연산을 수행해야겠죠

이런식으로 증명하던데요;

lacovnk의 이미지

complexity 측정대상은 time, storage 등이 될 수 있습니다.
성능이 무엇에 비례하느냐... 는 보통 input의 개수에 비례를 하지요.

그리고 위에서 지적했듯이, 가장 비싼 연산만 계산하면 됩니다. 알고리즘 책 초반에 보면 나옵니다~

M.W.Park의 이미지

위에서도 나온 말이지만, 알고리즘의 복잡도는 시간(time)과 공간(space)에서 측정됩니다.
대부분의 경우 두 요소 간에는 trade-off가 있고요.
특정 문제 도메인에서만 아주 높은 성능을 내는 알고리즘들도 있습니다.
(입력 집합의 특성같은 조건에 영향을 받는 것들)

현실적인 계산 완료 시간을 척도로 하는 것에 관한 질문이신거같은데,
big O notation으로 표기된 이론적인 시간복잡도에 입력의 개수를 넣고 적정한 상수를 곱하면 현실적인 시간으로 간주될 수 있습니다. 바꾸어, 뒤집어 말하면 입력의 개수를 변경하면서 현실적인 시간을 측정하면 big O notation이 어찌 생겼을 지도 어느 정도 짐작가능합니다.

-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂

-----
오늘 의 취미는 끝없는, 끝없는 인내다. 1973 法頂

merius의 이미지

input 갯수 - 걸린 시간 그래프가 있으면 되겠네요
다른 사항이 필요가 없다면....
그래프와 실제 값... 가장 중요한 것 같습니다.

Regards,
merius

Regards,
merius

rhheo의 이미지

결론부터 말씀드리면 "몇번 비교했나"라는 표현보다
"몇 스텝을 돌아야하나"라고 하는 것이 알기 쉽지 않을까합니다. (스텝 : 라인수가 아니구 알고리즘 실행의 기본 단위)
스텝을 나누는 기준으로 비교문이 자주 기점이 되기 때문에
비교했냐라는 말이 나왔나 봅니다.
저두 학부때 "몇번 비교했나"로 강의를 들었기 때문에 이해불가~~ (@.@) 했었던 기억이 있네요.

여튼 알고리즘을 분석한다는 의미는 이렇습니다.

어떤 알고리즘에
1. n개의 입력이 있으면
2. 얼만큼의 컴퓨터 자원을 사용하느냐(실행시간, 메모리 사용)
를 도출하는 것입니다.

예를 들면 선택정렬(
1. 리스트에서 최소값을 찾는다
2. 리스트의 첫번 째 값과 1에서 찾은 값을 스왑한다.
3. 나머지 리스트의 요소들도 위의 처리를 반복한다.
) 에서는

첫번째에는 최소값을 찾기 위해 n-1스텝을 실행합니다.
두번째에는 위의 값을 제외한 최소값을 찾기 위해 n-2스텝을 실행합니다.
마찬가지로 n-3, n-4, n-5 ...2, 1까지의 스텝을 실행합니다.
결과적으로 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2스텝이 걸리게 됩니다.

n개 기준의 실행 스텝수로 계산함으로써 컴터 시스템, 언어, 구현에 관계없는 분석이 이루어지는 겁니다.

그래서 "비교한 수"라고 하는 것은 실제로는 "실행된 스텝수"를 의미하는 겁니다.

참고로... 각 알고리즘 별로 n에 대한 스텝수를 계산한 결과를 분류해서
Big-O로 표기하는 방법을 사용하고 있습니다.
(위의 예에서는 n의제곱에 비례해서 스텝수가 실행 되어야하므로(O(n*n)) 썩 좋은 성능은 기대하기 어렵습니다.)

메모리는 스왑용 1개가 필요하겠군요. 마찬가지로 Big-O표기로 분류합니다.

rhheo의 이미지

질문의 예에서는
A[0,1,2,3,4..........n]

정렬이 되어 있네요...;;
한 스텝에 찾을 수 있으므로 O(1)이 되겠습니다.

정렬이 안되어 있다면
n단계의 스텝을 거쳐야 하므로 O(n)이 되겠군요.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.