voidBubbleSort(int* a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
int exchange = 0;
for (size_t i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0) {
break;
}
}
return;
}
按照计算步骤，先算总的执行次数，通过代码我们看到，还是需要分类考虑：
最好情况：进入外面的 for 循环一次，里面的循环需要走 end 次，总的执行次数就是 end+1 次；
最坏情况：那就只能把循环走完了！总的执行次数也就是 end^2 次。
再根据计算规则，取最坏情况，得到最后的时间复杂度为 O(N^2)。
易错点：经常以为双层 for 循环就是 N^2 了，一层 for 循环就是 N 次，但是需要避雷这个，具体情况需要具体分析。
第七题
intBinarySearch(int* a, int n, int x) {
assert(a);
int begin = 0;
int end = n;
while (begin < end) {
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x) {
begin = mid + 1;
} elseif (a[mid] > x) {
end = mid;
} elsereturn mid;
}
return-1;
}
首先我们先来计算它的总次数，根据这个代码情况，属于二分查找，还是需要分类：
最好情况：那肯定就一次找到，总执行次数就是 1 次；
最坏情况：对一组数据一直二分下去，要找的元素在数组最后一个被检查的位置。
假设数组长度为 N，每经过一次二分，剩余元素为 N/2，经过 k 次后，剩余元素为 N/(2^k)。
最坏情况也就是当剩余元素为 1 时，即 N/(2^k)=1。
解得 k=log N（注意 log N 在复杂度里面是等于以 2 为底 N 的对数的）。
按照计算规则，取最坏情况，得到最后的时间复杂度为 O(log N)。
第八题
longlongFactorial(size_t N) {
return N < 2 ? N : Factorial(N - 1) * N;
}
首先根据计算步骤，计算总的执行次数，我们发现这是一个三目操作符，我先来简单解释一下它的运算思路：
如果 N<2，为真就得到结果 N，如果为假就得到结果 Factorial(N-1)*N。
因此我们发现这是一个计算前 n 项阶乘的递归函数，下面我们来分析：
最好情况：直接执行一次，即计算 1 的前 n 阶乘；
最坏情况：假设有 N 个数字，那么它的阶乘就是 N*(N-1)(N-2)(N-3)...，执行了 N 次。
根据计算规则，保留最坏情况，得到最后的时间复杂度为 O(N)。
计算空间复杂度
第一题
voidBubbleSort(int* a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
int exchange = 0;
for (size_t i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0) {
break;
}
}
return;
}
intmissingNumber(int* nums, int numsSize) {
int sum = 0; //求和for (int i = 0; i <= numsSize; i++) {
sum += i;
}
//求差for (int i = 0; i < numsSize; i++) {
sum -= nums[i];
}
return sum;
}
