#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace chrono;
// O(n)
void function1(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        k++;
    }
}

// O(n^2)
void function2(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            k++;
        }
    }

}
// O(nlogn)
void function3(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 1; j < n; j = j*2) { // 注意这里j=1
            k++;
        }
    }
}
int main() {
    long long n; // 数据规模
    while (1) {
        cout << "输入n：";
        cin >> n;
        milliseconds start_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        function1(n);
//        function2(n);
//        function3(n);
        milliseconds end_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        cout << "耗时:" << milliseconds(end_time).count() - milliseconds(start_time).count()
            <<" ms"<< endl;
    }
}

面试题：求x的n次方 （重点关注时间复杂度，超不超int范围就先不考虑）

（1）for循环，O(n)
int function1(int x, int n) {
    int result = 1;  // 注意 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
        result = result * x;
    }
    return result;
}

（2）递归算法，时间复杂度O(n)
int function2(int x, int n) {
    if (n == 0) {
        return 1; // return 1 同样是因为0次方是等于1的
    }
    return function2(x, n - 1) * x;
}
递归n次，每次操作一个乘法 n * 1

（3）递归算法，时间复杂度O(n)
int function3(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;

    if (n % 2 == 1) {
    	//还剩奇数次
        return function3(x, n / 2) * function3(x, n / 2)*x;
    }
    //还剩偶数次
    return function3(x, n / 2) * function3(x, n / 2);
}
这个算法其实就是二分，每次将要计算的指数对半砍，可以用二叉树模拟
由于每次递归都是只做1个乘法，所以时间复杂度就是递归次数（二叉树的节点数）
如果二叉树的深度为m，从0开始，那么节点数为： 2^m + 2^m-1 + ... + 2^0 = 2^m+1 - 1
由于要计算n次方，所有 m = log2n - 1，代入上式，节点数为n-1

（4）递归算法，时间复杂度O(logn)
int function4(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
    if (n % 2 == 1) {
        return t * t * x;
    }
    return t * t;
}
每次二分，时间复杂度为O(logn)

O(1)的空间复杂度
int j = 0;
for (int i = 0; i < n; i++) {
    j++;
}

O(n)的空间复杂度
int* a = new int(n);
for (int i = 0; i < n; i++) {
    a[i] = i;
}

O(logn)的空间复杂度
递归次数为logn时会出现

递归求斐波那契数列的性能分析
(1)递归
int fibonacci(int i) {
       if(i <= 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonacci(i-2);
}
时间复杂度：每次递归都是O(1)操作（加法而已），主要看递归次数
由于这个函数逻辑是将i用i-1和i-2的递归调用来计算，那么其实就是二叉树
递归次数 = 二叉树节点 一颗高度为k（根节点为1）的二叉树最多有 2^k - 1个节点
所以时间复杂度为O(2^n)，空间复杂度O(n)

(2)记录前两次的值
int fibonacci(int first, int second, int n) {
    if (n <= 0) {
        return 0;
    }
    if (n < 3) {
        return 1;
    }
    else if (n == 3) {
        return first + second;
    }
    else {
        return fibonacci(second, first + second, n - 1);
    }
}
时间复杂度O(n),空间复杂度O(n) n次递归，每次都要传递两个数字

int binary_search( int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x);
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}
时间复杂度：O(logn) 每次递归只做判断 O(1) 二分递归O(logn)
空间复杂度：O(logn) 递归深度O(logn) 每次传参：O(1)