寒域爷最近突然精神抖擞，写下了大篇代码。刚刚学完时间复杂度的JM试图在一晚上弄懂寒域爷在代码中蕴含的深邃的思想，但是它却难以分析寒域爷的代码。于是愤怒的JM把你抓来了，要你为他讲解寒域爷代码的时间复杂度，如果他听不懂的话就把你喂给寒域爷制造更多的代码。
代码1
该函数出自两年前的ACM小学期课程中，用于实现求从1加到x的和
int sum(int _Xx) {
int ret = 0;
for (int i = 1; i <= _Xx; i++) ret += i;
return ret;
}
代码2
代码1被寒域爷魔改后，大大降低了时间复杂度，仍然是用于实现求从1加到x的和
inline int sum(int _Xx) { return (1 + _Xx) * _Xx / 2; }
代码3
这一坨代码出自刚刚接触C语言的小透明寒域，该函数用于将arr数组中的num个元素排序
void bubble_sort(int* arr, int num) {
for (int i = 0; i < num - 1; i++)
for (int j = 0; j < num - i - 1; j++)
if (arr[j] < arr[j + 1]) arr[j] ^= arr[j + 1] ^= arr[j] ^= arr[j + 1];
}
代码4
在寒域爷偶然间翻看自己以前写的破烂代码的时候，他将代码3修改成了下面的样子。该函数用于将arr数组中的num个元素排序
std::priority_queue 支持以O(logn)的时间复杂度插入任意元素，删除最小元素和O(1)的时间复杂度查询最小的元素。
#include <queue>
void heap_sort(int* arr, int num) {
std::priority_queue<int> heap;
for (int i = 0; i < num; i++) heap.push(arr[i]);
for (int i = 0; i < num; i++) {
arr[i] = heap.top();
heap.pop();
}
}
代码5
这个代码出自寒域爷闲暇时候用来测试Node.js语言和C语言的速度差距。该函数用于求斐波那契数列的第x项
long long int fibonacci(int _Xx) {
if (_Xx <= 2) return 1;
return fibonacci(_Xx - 1) + fibonacci(_Xx - 2);
}
代码6
JM看到寒域的垃圾代码后劈头盖脸训斥了寒域一顿，并修改成了下面的函数。该函数用于求斐波那契数列的第x项(x<1000)
#include <cstring>
long long int fibonacci(int _Xx) {
static long long int save[1000];
static bool first = true;
if (first) first = false, memset(save, -1, sizeof(save));
if (save[_Xx] != -1) return save[_Xx];
if (_Xx <= 2) return 1;
return save[_Xx] = fibonacci(_Xx - 1) + fibonacci(_Xx - 2);
}
代码7
该函数用于计算最长的每个字母最多出现一次的子字符串的长度，出处已经不可考。
#include <string>
int lengthOfLongestSubstring(std::string s) {
int i, j, len = 0, maxx = 0;
bool sign[30];
memset(sign, 0, sizeof(sign));
for (i = 0, j = 0; j < s.length(); ++j) {
while (sign[s[j] - 'a'] == 1) {
sign[s[i] - 'a'] = 0;
++i;
}
sign[s[j] - 'a'] = 1;
maxx = std::max(maxx, j - i + 1);
}
return maxx;
}