[완료] 합집합을 구하는 알고리즘

kimkyoungjo의 이미지

두개 집합의 합집합을 구하는 알고리즘 O(n lg n) 을 구하는 레포트가 있는데
안굴러가는 머리를 굴려보면 일단 두개 집합(두개의 배열)을 연결해서 하나의 배열로 만든다음에
randomized quick sorting 해서 같은 원소들을 지우면 완성! 이라고 생각하는데요~
여기서 두가지 질문이 있습니다

1. randomized quick sort 의 시간복잡도는 O(n lg n) 이라고 봐야하나요?
아니면 O(n^2) 라고 봐야하나요?
expected time complexity 는 O(n lg n) 이라고 하지만
단순히 시간복잡도라고만 하면 O(n^2) 인가요?

2. 위에 써놓은대로 알고리즘을 짜면 시간복잡도가 O(n lg n) 이 될까요?

답변해주시면 복받으실꺼예요 ㅠ_ㅠ

asiawide의 이미지

set 자료구조가 이미 있습니다. 알고리즘 책에도 많이 나오고 인터넷에도 찾아보시면 있을 것입니다. -.-

kimkyoungjo의 이미지

그런걸 찾아서 하라는 말은 아닌것 같습니다
자신이 스스로 생각해보고 찾아서 자신의 논리를 일목요연하게 보여라
라는 취지에서 문제를 내신게 아닐까 생각합니다만 ㅠ_ㅠ

netionics의 이미지

엄밀히 따지면 빅오표기법은 최악의 경우를 가리키고 이미 정렬된 집합에서 O(N^2)속도를 보이는 퀵정렬이라면 O(N^2)가 맞겠지요.
이를 해결한 퀵정렬이라면 물론 달라집니다. 도서관 가셔서 관련 서적을 더 찾아보세요. 답이 훨씬 풍부해질 겁니다. :)

:)

clique의 이미지

balanced binary tree계열이 보통 logn의 탐색, 삽입, 삭제를 지원하므로 아무거나 구현하시면 해결이 되리라 봅니다.

vacancy의 이미지


MergeSort를 잘 활용해보시면 쉽게 풀릴것 같네요.

kimkyoungjo의 이미지

무지 복받으실 꺼예요~
감사합니다

임창진의 이미지

자료구조 보시는김에 skiplist 라는 것도 한번 살펴 보세요 이걸 만든사람말에 의하면 "Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space." 이렇다고 합니다.

http://kldp.org/node/81810 이 문서의 개발팀 2번 문제의 답을 내놓을수도 있을 것 같습니다.

댓글 달기

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