本文发表在 rolia.net 枫下论坛n is the # of regular numbers that is needed to put in the array, the running time should be proportional to n, that is it must be in the form of 'an + b', where a and b are constants, however, the running time can't be one of these: n^2, n^3, n*log n, etc... in other words, what you do to each one of the n numbers should be a constant time, result a total running time of O(n)
for example, the following code takes O(n log n) times, because the running time of the while loop isn't constant, it depends on the value of a,
void regular(int R[], int n) {
int i = 0;
for(int a = 1; i < n; a++) {
int b = a;
while(b != 1) {
if (b % 2 == 0)
b = b / 2;
if (b % 3 == 0)
b = b / 3;
if (b % 5 == 0)
b = b / 5;
else break;
}
if (b == 1) {
R[i] == a;
i = i + 1;
}
}
}更多精彩文章及讨论，请光临枫下论坛 rolia.net
for example, the following code takes O(n log n) times, because the running time of the while loop isn't constant, it depends on the value of a,
void regular(int R[], int n) {
int i = 0;
for(int a = 1; i < n; a++) {
int b = a;
while(b != 1) {
if (b % 2 == 0)
b = b / 2;
if (b % 3 == 0)
b = b / 3;
if (b % 5 == 0)
b = b / 5;
else break;
}
if (b == 1) {
R[i] == a;
i = i + 1;
}
}
}更多精彩文章及讨论，请光临枫下论坛 rolia.net