परिशोधित विश्लेषण क्या है?
ऑपरेशन के अनुक्रम के लिए औसत समय जटिलता, भले ही कुछ ऑपरेशन महंगे हों। यह औसत-मामला विश्लेषण नहीं है, बल्कि कई ऑपरेशनों पर वितरित सबसे खराब स्थिति है।
बाइनरी काउंटर उदाहरण
k-बिट बाइनरी काउंटर पर इंक्रीमेंट ऑपरेशन। अंतिम बिट से पहला 0 ढूंढें, उसे 1 बनाएं और बाद के सभी बिट्स को 0 करें।
उदाहरण: 00000000 → 00000001 → 00000010 → 00000011 → 00000100 → ...
विश्लेषण
- पहला बिट हर बार फ्लिप होता है: n बार
- दूसरा बिट हर दूसरी बार: n/2 बार
- तीसरा बिट हर चौथी बार: n/4 बार
- कुल फ्लिप: n + n/2 + n/4 + ... < 2n
- परिशोधित लागत प्रति ऑपरेशन: O(2n)/n = O(1)
उदाहरण कोड
#include <iostream>
using namespace std;
int main() {
int number[] = {1, 0, 0, 1, 0, 1, 1, 1};
int length = 8;
int i = length - 1;
while (number[i] == 1) {
number[i] = 0;
i--;
}
if (i >= 0)
number[i] = 1;
for (int i = 0; i < length; i++)
cout << number[i] << " ";
return 0;
}
आउटपुट
1 0 0 1 1 0 0 0
