数据结构慢慢啃(step 3)

衡量一个算法的好坏, 从时间复杂度和空间复杂度来全面分析,
算法的最优解: 先考虑时间复杂度再考虑空间复杂度

时间复杂度

常数阶O(1) : 算法的执行时间总是为常数, 不随数据量变化而改变

int k = i + j;
复制代码

线性阶O(n) : 算法的执行时间随数据量的变化线性增长

for (int i = 0; i < n; i++) {
    //TODO
}
复制代码

平方阶O(n^2) :

for(int i = 1; i <= n; i++) {
   for(int j = 1; j <= n; j++) {
      //TODO
   }
}
复制代码

对数阶O(logn) : 2^x = n 得出 x = log₂n, while循环处理不一定都是线性的

int i = 1;
while (i < n) {
    i = i * 2;
}
复制代码

PS: N^M 就是 N * N * N ....(M个N相乘, 感觉都把数学内容都还给老师了)

线性对数阶O(n * logn) : 把时间复杂度为logn代码循环n遍

for(int m = 1; m < n; m++) {
    i = 1;
    while(i < n) {
        i = i * 2;
    }
}
复制代码

空间复杂度

常数阶O(1) :

int i = 1;
int j = 2;
int m = i + j;
复制代码

线性阶O(n) :

int[] m = new int[n]
for(int i = 1; i <= n; ++i) {
   int j = i;
   j++;
}
复制代码