Time complexity와 관련해서 질문드립니다.

  • danielseol
    danielseol

    for(i ; i <n; i++){

    printf("algospot");

    }
    위의 경우, 시간 복잡도는 O(n)입니다.

    그러면,

    for(i ; i < n; i++){
    qsort(data);
    }
    심한 예를 들어서, 이 경우에는 시간복잡도를 O(n)이라고 해야하는지..

    아니면, qsort를 nlogn이라고 생각해서 O(n^2logn)이라고 해야하는 지
    궁금합니다.

    ACM 이나 이 사이트에서 문제를 풀때와 관련해서 답변해주시면 감사드리게습니다.


    3년 전
5개의 댓글이 있습니다.
  • riceluxs1t
    riceluxs1t

    JMB을 사서 공부를 조금 더 하시는걸 추천합니다.


    3년 전 link
  • Being
    Being

    결론만 말하자면 후자에 가깝습니다. 시간 복잡도란 사칙연산, 비교, 대입과 같은 "상수 시간"이 걸리는 연산을 몇 번이나 수행하는지에 대한 것이라 생각하시면 이해에 도움이 되실 겁니다.


    3년 전 link
  • 일루
    일루

    'Time' 이니까 후자가 가깝겠죠? 예외적인 케이스로 qsort만을 매우 효율적으로 수행하는 가상의 병렬연산유닛이 있어서 O(1)로 수행할 수 있다면 O(n)이 되겠지만요.


    3년 전 link
  • danielseol
    danielseol

    riceluxs1t ) 오늘 서점에 들려서 책을 찾아봤는데, 이미 다팔렸더군요. 다음번에 사서 참고하겠습니다. 감사합니다.

    Being ) 댓글을 몇번 곱씹어 생각해보니 이해가 가네요. 감사합니다.

    일루 ) 일루님도 감사합니다. 오늘 의문이 풀렸어요!


    3년 전 link
  • Being
    Being

    네, 엄밀히는 일루님이 말씀해 주셨듯 우리의 계산 모델이 할 수 있는 연산들과 그 소요 시간이 정의될 때 걸리는 시간이겠지만, 일반적으로 생각하는 건 다 상수 시간입니다.


    3년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.