3.1
不证明了
3.2
正确性不证了
如果不进行优化，那最坏复杂度和平均复杂度都是n2
冒泡排序代码如下：
//冒泡排序 void bubblesort(vector<int>& v) { for (int i = 0; i < v.size() - 1; ++i) { for (int j = 0; j < v.size() - i -1; ++j) { if (v[j] > v[j + 1]) { swap(v[j], v[j + 1]); } } } }
冒泡排序的一种优化方案：
//冒泡排序改进1，加入变量记录是否交换 void bubblesort1(vector<int>& v) { for (int i = 0; i < v.size() - 1; ++i) { bool right = true; for (int j = 0; j < v.size() - i - 1; ++j) { if (v[j] > v[j + 1]) { right = false; swap(v[j], v[j + 1]); } } if (right == true) return; } }
冒泡排序按书中3的方式进行优化：
//冒泡排序改进2，加入变量记录每次循环中最后发生元素交换的位置 //注意此处的写法，一定要每一个遍历周期对j的末位置进行一次替换，而不能直接使用last_swap_pos作为末位置 void bubblesort2(vector<int>& v) { int last_swap_pos = v.size() - 1; for (int i = 0; i < v.size() - 1; ++i) { int last_pos = last_swap_pos; for (int j = 0; j < last_pos; ++j) { if (v[j] > v[j + 1]) { last_swap_pos = j+1; swap(v[j], v[j + 1]); } } } }
两种优化方案的最坏复杂程度都没有变，任然是n2
如果要算平均复杂度，第一次要n的复杂度，第二次需要(n-1)/2次比较，第3次需要(n-2)/2，依次类推，求和得复杂度应该还是n2
3.3
煎饼排序问题，据说这个问题的作者是比尔盖茨
- 当只有一个煎饼的时候很容易可以正确
- 假设当有n个煎饼的时候成立，当有n+1个煎饼的时候，找到最大的煎饼，假设最大的煎饼在k处，从k处翻一下，可以使最大的煎饼冒到最上层，然后全部n+1个煎饼翻一下，则最大的煎饼处在最下层，接着使用已知结论，n个煎饼时成立，可以使上面n个煎饼有序，所以证明了n+1时成立。
复杂度分析：首先遍历一遍找到最大的煎饼需要n的复杂度，最大的煎饼翻到最下层需要2次操作，类推一下，复杂度应该为n2
3.4
遍历到数n1时，查看前一个数n2，如果n2>n1，则n2处的结果应该为它的前项，否则查看结果数组result，使用n1去和result[n1]处的比较
//pervious-larger vector<int> perviouslarger(vector<int>& v) { vector<int> result(v.size(),0); for (int i = 1; i < v.size(); ++i) { int pos = i - 1; while (v[result[pos]] < v[i]) { pos = result[result[pos]]; if (pos == 0) break; } result[i] = pos; } return result; } //这是测试用例 int main() { vector<int> v = {4,2,1,6,3,9}; auto result = perviouslarger(v); for (auto i : result) { cout << i << endl; } system("pause"); return 0; }
3.5
这题就遍历一遍，把字符串分割成多个单词，加入到数组中，最后逆序输出就可以了吧。
时间复杂度和空间复杂度都是n
3.6
应该是只能有一个吧
暴力解法：遍历每个人的关注列表，找出一个都没有关注的人
优化解法：选取其中任一人，依次询问他是否关注了其他人，得到他关注的人的列表，名人必定在这个列表之中，如果他都没有关注，那么他就是名人，然后对该列表中的每个人重复上述步骤，对每个列表取交集，不断缩小，直至列表只有一个人。
3.7