2
나는이 algorithm의 시간 복잡도를 찾으려고합니다.반복 알고리즘의 시간 복잡도
반복 : 알고리즘은 주어진 비트 - 스트링으로부터 주어진 해밍 거리 내의 모든 비트 - 스트링을 생성합니다. 모든 증가 시퀀스 0 <= a[0] < ... < a[dist-1] < strlen(num)을 생성하고 해당 인덱스의 비트를 되돌립니다.
벡터 a은 어떤 비트가 반전되어야하는지에 대한 색인을 유지해야합니다. 따라서 a에 현재 색인 i이 포함되어 있으면 0 대신 1을 인쇄하고 그 반대로 인쇄합니다. 그렇지 않으면 아래와 같이 비트를 인쇄합니다 (else-part 참조).
// e.g. hamming("0000", 2);
void hamming(const char* num, size_t dist) {
assert(dist > 0);
vector<int> a(dist);
size_t k = 0, n = strlen(num);
a[k] = -1;
while (true)
if (++a[k] >= n)
if (k == 0)
return;
else {
--k;
continue;
}
else
if (k == dist - 1) {
// this is an O(n) operation and will be called
// (n choose dist) times, in total.
print(num, a);
}
else {
a[k+1] = a[k];
++k;
}
}
이 알고리즘의 시간 복잡도는 얼마입니까?
내 시도는 말한다 :
DIST * n 개의 +는 (N t 선택) * N + 2
그러나 이것은 사실이없는 것, 모든, 다음 예를 고려 with dist = 2 :
len = 3, (3 choose 2) = 3 * O(n), 10 while iterations
len = 4, (4 choose 2) = 6 * O(n), 15 while iterations
len = 5, (5 choose 2) = 9 * O(n), 21 while iterations
len = 6, (6 choose 2) = 15 * O(n), 28 while iterations
다음은 두 가지 대표적인 실행입니다 (sta에서 인쇄 될 예정 임). 루프 RT)
000, len = 3
k = 0, total_iter = 1
vector a = -1 0
k = 1, total_iter = 2
vector a = 0 0
Paid O(n)
k = 1, total_iter = 3
vector a = 0 1
Paid O(n)
k = 1, total_iter = 4
vector a = 0 2
k = 0, total_iter = 5
vector a = 0 3
k = 1, total_iter = 6
vector a = 1 1
Paid O(n)
k = 1, total_iter = 7
vector a = 1 2
k = 0, total_iter = 8
vector a = 1 3
k = 1, total_iter = 9
vector a = 2 2
k = 0, total_iter = 10
vector a = 2 3
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[email protected]:~/Desktop/generate_bitStrings_HammDistanceT$ ./iter
0000, len = 4
k = 0, total_iter = 1
vector a = -1 0
k = 1, total_iter = 2
vector a = 0 0
Paid O(n)
k = 1, total_iter = 3
vector a = 0 1
Paid O(n)
k = 1, total_iter = 4
vector a = 0 2
Paid O(n)
k = 1, total_iter = 5
vector a = 0 3
k = 0, total_iter = 6
vector a = 0 4
k = 1, total_iter = 7
vector a = 1 1
Paid O(n)
k = 1, total_iter = 8
vector a = 1 2
Paid O(n)
k = 1, total_iter = 9
vector a = 1 3
k = 0, total_iter = 10
vector a = 1 4
k = 1, total_iter = 11
vector a = 2 2
Paid O(n)
k = 1, total_iter = 12
vector a = 2 3
k = 0, total_iter = 13
vector a = 2 4
k = 1, total_iter = 14
vector a = 3 3
k = 0, total_iter = 15
vector a = 3 4
+1. Re : "N_INCR_SEQ (n, dist)는 자연수의 증가 시퀀스의 길이입니다.
ruakh
덧붙여 말하자면, 분석의 한 의미는'if (++ a [k]> = n)'행을'if (++ a [k] = n)'행으로 변경하여 OP가 코드의 성능을 최소한으로 수정할 수 있다는 것입니다. > n - dist + k)'를 선택하십시오. 그러면 불필요한/비생산적인 앞뒤 패스가 모두 제거됩니다. – ruakh
실제로 @ruakh,하지만 나는 Paul의 코드가 더 마음에 든다. 내 젊은 눈보다 우아 해 보인다! O ((n choose dist) * n)의 전체 시간 복잡도 ... – gsamaras