저는 코딩과 관련된 도전을하고있었습니다 : 경마 듀얼. 목표는 목록의 두 요소 간의 최소 차이를 찾는 것입니다.
나는이 첫 번째 알고리즘으로 시작했는데, 그것은 내가 생각 O(nlog(n))하지만 큰 배열에 대한 실행 시간이 초과되었습니다.
int array[N];
int min = numeric_limits<int>::max();
for (int i = 0; i < N; i++) {
int value;
cin >> value;
cin.ignore();
array[i] = value;
for (int j = i - 1; j >= 0; --j) {
int diff = abs(array[j] - value);
if (diff < min) {
min = diff;
}
}
}
그런 다음이 다른 알고리즘을 시도 O(nlog(n))했으며 이번에는 실행이 제 시간에 완료됩니다.
int array[N];
int min = numeric_limits<int>::max();
for (int i = 0; i < N; i++) {
int value;
cin >> value;
cin.ignore();
array[i] = value;
}
sort(array, array + N);
for (int i = 1; i < N; ++i) {
int diff = abs(array[i - 1] - array[i]);
if (diff < min) {
min = diff;
}
}
첫 번째 코드 복잡성에 문제가 있습니까? 내가 눈치 채지 못한 차이점이 있습니까?
당신의 도움을 주셔서 감사합니다.
첫 번째 코드 복잡성에 문제가 있습니까?
네, 틀 렸습니다.이 복잡성은 O (n log n) 이 아니라 O (n ^ 2) 입니다.
외부 루프는 n ( N) 번 실행되고 내부 루프는 평균 n / 2 번 실행됩니다 . 따라서 복잡도는 곱셈 상수가 복잡도 계산에서 중요하지 않기 때문에 O (n * n / 2) 이며 O (n ^ 2) 입니다.
눈치 채지 못한 차이점이 있습니까?
네, 있습니다. O (n log n) 과 같이 매우 동일한 복잡성을 가진 두 개의 알고리즘이 있더라도 점근 적 복잡성 동작에서 무시되는 숨겨진 상수로 인해 둘 다 매우 다른 시간에 실행될 수 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다