현재 위치

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

빅오표기법/알고리즘 관련 책/글 추천 부탁드립니다!

kbm1378의 이미지
글쓴이: kbm1378 / 작성시간: 수, 2015/01/07 - 4:45오후

안녕하세요.

빅오표기법/알고리즘과 관련하여 책을 추천받고자 글을 썼습니다.

사실 알고리즘 관련 책 추천 글이 하나 있긴 했는데 제가 공부하고자하는 부분이 조금 더 specific한 부분이어서 그거에 관한 책이 있을지 여쭤보고 싶어서요.

제가 지금 하려고 하는 일은 java bytecode instruction으로부터 Loop를 찾고 그 Loop로 부터 Big-O notation을 가져와 소스의 복잡도를 보려고 합니다.

이와 관련해서 디컴파일러도 좀 보고 있고 이제 어느정도 Loop는 찾아서 그 Loop의 복잡도를 보려고 하는데,

전 단순히 For문 => N 루프. 이런식으로 처리하려고 하였는데 이게 또 중첩 FOr문에서 관계에 따라 다 달라지더군요 ㅠㅜ

그래서 그런거와 관련하여 조금 더 지식을 쌓아야 할것 같아서요.

혹시 이와 관해 참고하면 좋을 책이나 글이 있다면 추천 부탁드립니다! 감사합니다!

- 빅오표기법 관련 전공도서/참고도서
- 소스를 파싱해서 빅오표기법을 구해내는 소프트웨어/오픈소스/방법에 관한 글

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

글쓴이: yukariko / 작성시간: 목, 2015/01/08 - 2:55오전

어디까지나 제 생각입니다만..
소스코드를 파싱해서 시간복잡도를 구해내는건
어셈블리코드를보고 c언어 소스를 복구하는것만큼 어렵지않을까 싶네요..
실제로 어셈블리로 c언어소를짜는 프로그램이 있다고 들었습니다만 그것도 알고보니 다양한 어셈블리패턴을 집어넣고 그것으로 복구를한다고 하더군요. 물론 제대로 되진않겠죠..
이것도 비슷한 상황이라고 봅니다.
단순히 for i <= n 인 포문은 바로 구해낼 수 있다지만, 그 안에서 n의 값또한 조절된다면?
그외에도 예외적인케이스는 매우많겠죠..

소스를 파싱하는방법말고 변수의 수치에따른 수행 시간을 측정해서 그래프를 그리고 그 그래프를토대로 시간복잡도를 측정한다면 어느정도 해결책이 보이지않을까 생각해봅니다.

jick의 이미지

글쓴이: jick / 작성시간: 목, 2015/01/08 - 3:06오전

Big-O notation은 정말 아무 알고리즘 책이나 보면 다 나오니까 하나 사보시면 되고요, 무거운 책도 괜찮으시다면 CLRS 추천합니다. (구글에 CLRS라고 치시면 나옵니다.)

근데 위의 분이 말하셨듯이 "루프를 보고 시간복잡도를 구하는 것"은 단순히 big-O notation을 안다고 되는 일이 아닌데요. Halting problem에 맞먹습니다. 뭐, 간단한 케이스에 한해서 패턴 매칭을 해서 "이 경우는 복잡도가 얼마"라고 알려줄 수는 있겠지만 그 "간단한 케이스"를 나열하기만 해도 엄청난 작업이 될 것 같습니다만...

(Halting problem: 주어진 코드를 보고 이 프로그램이 언젠가는 끝날지 아니면 무한 루프를 돌지 알아맞추는 문제. 해결이 *불가능하다는 것이* 증명되어 있음.)

댓글 달기

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

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