현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

자료구조와 알고리즘 (알고리즘 성능 분석에 대해)

alfhd00의 이미지
글쓴이: alfhd00 / 작성시간: 수, 2015/12/16 - 11:19오전

시간 복잡도를 표현하는 표기 방식이 총 3가지가 있습니다. (빅오, 빅 오메가, 빅 세타)
시간 복잡도를 나타내는 경우도 3가지 있습니다. (최상, 최악, 평균 / 그 중에서 최악이 제일 많이 쓰이고요)

그런데 빅오 표기법으로 최악의 경우를 나타낸다고 합니다.

제가 궁금한 것은 무조건 빅오는 최악, 빅 오메가는 최상, 빅 세타는 평균을 표현하도록 정의되어 있나요?

제가 가지고 있는 자료에서 순차탐색의 시간 복잡도를 설명하는 부분이 있는데

최선의 경우 : 찾고자 하는 숫자가 맨 앞에 있는 경우 : O(1)

최악의 경우 : 찾고자 하는 숫자가 맨 뒤에 있는 경우 : O(n)

평균적인 경우 : (n+1)/2 : O(n)

이렇게 기술되어 있어요. 각 경우에 따른 빅오 표기법을 보여주고 있는데

꼭 빅오 표기법이 최악의 경우를 말하는 것 같지 않는데요?

제가 어느 부분을 잘못 이해하고 있는 걸까요?

Forums: 
프로그래밍 QnA
jeff_an의 이미지

글쓴이: jeff_an / 작성시간: 수, 2015/12/16 - 11:57오전

"소수분포 연구에서 나온 란다우 기호(Order 표기법)은 '변화의 유형'을 표기하기 위한 뛰어난 수단입니다, 알고리즘에선 계산량에 관하여 사용하지만, 여러 분야에서 폭 넓게 사용됩니다."
이 책에 의한 Order 표기법 정의는 최악을 나타내는 경우가 아니라 변화의 유형을 표기하기 위한 수단이므로 최선/최악/평균의 경우에 사용될 수 있는 것 같네요.

jick의 이미지

글쓴이: jick / 작성시간: 수, 2015/12/16 - 2:02오후

O/Theta/Omega는 각각 정해진 의미가 있습니다. 그 의미가 최악/최상/평균과 비슷하게 들리긴 하지만 엄밀하게 정의로 따져 보면 서로 다른 이야기입니다. 그러므로 최악에도 Omega를 쓸 수 있고 최상에도 O를 쓸 수 있습니다.

위에 예로 드신 경우에는 사실 최선/최악을 O(1)과 O(n) 대신 Theta(1)과 Theta(n)으로 쓸 수 있습니다. 평균의 경우도 "모든 경우의 평균을 구하면 (n+1)/2이므로 Theta(n)이다"라고 할 수 있습니다.

어떤 함수가 Theta(f(n))에 속하면 정의에 의해 당연히 O(f(n))에 속하기 때문에, 많은 경우 사실 Theta라고 쓰는 게 좀 더 정확할 부분에 그냥 관습적으로 O를 쓰고 읽는 사람이 알아서 알아 들어라... 하는 경우가 꽤 있습니다.

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.