알고리즘은 정수와 문자열을 동일한 시간 일관성으로 정렬합니까?

Question

나는 바보 같은 질문 일지 모르지만 알고리즘이 5 초 안에 100,000 개의 정수를 정렬한다고 가정 해 봅시다. 같은 알고리즘이 5 초 만에 100,000 개의 문자열을 정렬합니까, 아니면 정렬 시간이 다를 것입니까?

Answer 1

문자열 비교는 정수 비교보다 비쌉니다. 정수 비교는 일반적으로 CPU에서 발생하는 연산입니다. 반면에 문자열 비교는 소프트웨어로 구현해야합니다. 따라서 문자열 비교는 문자열에있는 문자만큼 많은 작업을 수행 할 수 있습니다.

--dmg

Answer 2

간단한 대답은 아니오입니다. 문자열 정렬은 일반적으로 정수 정렬보다 훨씬 오래 걸립니다.

"paper"와 "papa"를 정렬하는 것을 고려하십시오. "paper"가 처음 4자를 비교하여 "papa"보다 더 큰 것을 알아야합니다. 큰 문자열, 특히 문구를 사용하면 더 길어질 수 있습니다.

대조적으로 정수 비교는 단일 명령을 사용합니다.

정렬을 수행하려면 이러한 종류의 비교를 반복해야합니다. 그래서 문자열 정렬은 거의 항상 더 오래 걸릴 것입니다.

Answer 3

문자열은 더 많은 시간이 걸릴 것입니다. 정수는 비트 연산 집합과 비교됩니다. 문자열과 관련하여 각 바이트 또는 문자는 정수에 필요한만큼 동일한 연산과 비교되어야합니다.

사실상, 문자열 집합을 정렬하는 것은 최악의 경우 모든 문자열에서 총 문자 수를 비교하는 것을 포함합니다. 최악의 경우는 모든 문자열이 동일하다는 것입니다. 모든 문자열은 끝에 도달 할 때까지 동일해야합니다 (strcmp()는이 방식과 비교됩니다)

Answer 4

Q : 알고리즘은 정수와 문자열을 같은 시간 일관성으로 정렬합니까?

A : 의미하는 경우 "asymptotic"/"Big O notation" : 예. 문자열은 분명히 오래 걸릴 것입니다 ... 그러나 비례하여 길어.

Answer 5

사전 순으로 정렬하고 빠른 정렬을 사용한다고 가정합니다. 문자열과 정수를 비교하는 자체 비교 함수를 작성합니다.

정수는 매우 간단합니다. 문자열의 값은 인덱스와 같지만 그 내용을 비교해야합니다. 빠른 정렬은 O (nlogn)의 평균 시간 복잡도에서 실행되며, 최악의 경우 O (n^2)이며, 선택한 피벗이 현재 파티션의 최소 또는 최대 일 때 발생합니다. 모든 것이 순조롭게 진행된다고 가정 할 것이고, 현재 우리는 평균적인 사건을 가지고 있습니다.

시간 복잡도는 비교 함수입니다. 정수는 O (1)이 가장 빠르며, 문자열을 비교하는 것은 O (min (len (a), len (b)), worst case 첫 번째 문자가 다른 경우 O (1)의 경우

그렇기 때문에 문자열을 고려하면 속도는 느리지 만 나쁜 것은 아니며 최악의 경우는 드물게 발생합니다. (Barney Goven은 , 두 개의 비슷한 문자열 비교)

알고리즘의 시간 복잡성에 대해 이야기 할 때, 우리는 일반적으로 데이터가 커지면 그 성장에 대해 이야기합니다 .paulsm4가 말했듯이, 비례하여 길어집니다.