수면 종류의 시간 복잡성은 무엇입니까?

수면 종류의 시간 복잡성은 무엇입니까?

---

이 정렬 알고리즘이 주어지면 시간 복잡성을 어떻게 표현합니까?

원래 여기에 표시되었습니다 (부분 아카이브) .

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

---

O(max(input)+n)

대부분의 정렬 알고리즘은 데이터에 구애받지 않기 때문에 복잡성은 표현하기 어색해 보입니다. 시간은 데이터 자체가 아니라 데이터 양에 따라 달라집니다.

FWIW 는 여기서 지적했듯이 데이터 정렬을위한 신뢰할 수있는 알고리즘이 아닙니다.

---

아무도 언급하지 않은 것으로 보이는 한 가지 요점은 이러한 sleeps가 구현되는 방법입니다. 궁극적으로 그들은 어딘가의 스케줄러에서 끝나고 운영상의 복잡성은 사용되는 스케줄링 알고리즘에 따라 달라집니다. 예를 들어, sleeps가 우선 순위 큐에 이벤트로 배치되면 복잡성 O (n log n) 으로 힙 정렬과 동일한 결과를 얻을 수 있습니다. 순진한 스케줄링 알고리즘의 결과는 O (n ^ 2) 입니다.

---

나는 paxdiablo가 가장 가깝다고 생각하지만 올바른 이유는 아닙니다. 시간 복잡성은 캐시 크기, 메모리 제한,이 경우 제한된 수의 프로세스 및 스케줄러 작동과 같은 실제 하드웨어의 문제를 무시합니다.

시간 복잡성 에 대한 Wikipedia 페이지를 기반으로하면 다음과 같이 정의되어 있기 때문에 런타임 복잡성을 결정할 수 없다는 대답이 있습니다.

시간 복잡도는 일반적으로 알고리즘에 의해 수행되는 기본 작업의 수를 계산하여 추정되며 기본 작업은 수행하는 데 고정 된 시간이 걸립니다. 따라서 알고리즘에 의해 수행되는 시간과 기본 연산의 수는 기껏해야 일정한 요소만큼 다릅니다.

그런 다음이 알고리즘의 런타임 복잡성에 대해 이야기 할 수 없습니다. 기본 작업에 걸리는 시간이 매우 다르기 때문에 걸리는 시간이 일정한 요소 이상으로 다를 수 있기 때문입니다.

---

해당 알고리즘의 시간 복잡성과 프로세스 복잡성은 O(braindead)다음 과 같습니다.

• 데이터 세트에 충분히 큰 값 이 있으면 해가 폭발 할 때까지 답변을 기다리고있을 것입니다 (2 ⁶⁴ 초는 5 조 5 천억 년이 조금 넘습니다).
• 데이터 세트 크기 가 충분히 크면 (a) 프로세스 한계에 도달합니다. 및 (b)는 후자의 사람들이 시작하기 전에 일찍 잠이 세트를 의미 종료됩니다 것을 발견 (2,9,9,9,9,9,...,9,9,1)하지 종류의 의지 1와 2올바르게.

이 경우 시간 복잡성은 관련이 없습니다. 당신은 할 수 얻을 수 있는 덜 "잘못"보다 최적화. 복잡성 분석을 사용하여 데이터 세트 크기가 변경 될 때 알고리즘을 비교하는 것은 괜찮지 만 알고리즘이 처음에 터무니없는 경우는 아닙니다. :-)

---

스레드를 읽으면 질문이 이미 답변 된 것을 볼 수 있습니다. 시간 복잡성은 O(max(input))이고 운영 복잡성 (작업 수)은 O(n)입니다.

---

선형처럼 보이지만 복잡성은 여전히 ​​O (log (n) * max (input))라고 생각합니다.

점근 적 시간 복잡성에 대해 이야기 할 때 n이 무한히 커질 때 걸리는 시간을 의미합니다.

비교 기반 정렬 알고리즘은 O (n * log (n))보다 빠를 수 없으며 Sleep-Sort는 실제로 비교 기반입니다.

프로세스는 n 초 동안 잠자고 깨어납니다. OS는 모든 수면 프로세스에서 가장 적게 남은 수면 시간을 찾아야하며 시간이되면 깨어나야합니다.

여기에는 요소를 삽입하는 데 O (logN) 시간이 걸리고 최소 요소를 찾는 O (1)과 최소 요소를 제거하는 O (logN)가 걸리는 우선 순위 큐가 필요합니다.

n이 매우 커지면 프로세스를 깨우는 데 1 초 이상이 걸리므로 O (n)보다 커집니다.

---

저는 Jordan과 함께합니다. 단, 벽시계 시간 복잡도는 O (2 ^ m)로 표현하는 것이 더 좋다고 생각합니다. 여기서 m은 O (max (input))이 아니라 각 항목의 크기입니다.

각 항목의 크기가 m이면 가장 큰 항목의 정수 값은 2 ^ m입니다 (마이너스 1이지만 아무도 신경 쓰지 않음). 구성에 따라 알고리즘은 설정 시간이 상수 인 1보다 작아야합니다.

따라서 벽시계 시간 복잡도 O (2 ^ m), 작업 횟수 복잡도 O (n).

설정 시간을 고려한 수정 된 알고리즘은 벽시계 시간 복잡성 O (2 ^ m + n)을 가질 수 있습니다. 예를 들어, 처음에 현재 시간을 기록하고 base_time = start_time + k*len(list)(적절한 상수 k에 대해) 계산 한 다음 스레드가 time까지 휴면하도록 할 수 있습니다 base_time+i. 그렇다면 k*len(list)분명히 O (n)이고 iO (2 ^ m)는 이전과 같이 총 O (2 ^ m + n)입니다.

참고 URL : https://stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort