编程导航算法通关村——算法基础

目录

1. 时间复杂度

1.1. 时间复杂度概念

1.2. 几种常见的阶

1.2.1. 常数阶 O(1)

1.2.2. 线性阶 O(n)

1.2.3. 平方阶 (n2)

1.2.4. 对数阶 O(logn)

2. 最坏情况和平均情况

3. 空间复杂度

---

1. 时间复杂度

1.1. 时间复杂度概念

当我们说算法的时间复杂度时，我们通常是指执行该算法所需的基本操作次数，而不是实际的时钟时间。为了估算这个时间复杂度，我们通常会找出算法中的基本操作，并计算其执行次数。

以下是一个简单的Java代码示例，用于计算从1到n的所有数字之和：

public class SumUpToN {  
    public static int sum(int n) {  
        int sum = 0;  
        for (int i = 1; i <= n; i++) {  
            sum += i;  
        }  
        return sum;  
    }  
  
    public static void main(String[] args) {  
        int n = 100; // 举例n为100  
        System.out.println("Sum up to " + n + " is: " + sum(n));  
    }  
}

在这个例子中，基本操作是sum += i，它在for循环中执行了n次。因此，该算法的时间复杂度是O(n)。这表示，如果我们将输入大小（这里是n）翻倍，那么基本操作的执行次数也会大致翻倍。

需要注意的是，时间复杂度是一个估算值，用于比较不同算法的效率。实际的运行时间还会受到其他因素的影响，如硬件速度、编程语言、编译器优化等。

---

除了用次数表示时间进行简化，还有一个系数和参数方面的简化。
例如y=x+1,当x非常大时，1就可以忽略不计了，可以只保留y=x。
而如果y=x^2+x，当x非常大时，后面的+x作用也不大了，可以只保留y=x^2。
同理，y=3x^2和y=x^2+x+4 ，当x非常大时，此时前面的系数3和4的影响也不大，我们仍然可以只保留y=x^2。
此时可以只考虑不同的阶之间的变化情况，如下可以看到过了1之后，不同的表达式的差异将非常巨大。

需要记住的是常见的阶耗费时间的关系是：

---

1.2. 几种常见的阶

1.2.1. 常数阶 O(1)

一般顺序执行并且只执行一次的代码就是常数阶

常数阶（O(1)）指的是算法的执行时间与输入数据的大小无关，也就是说，无论输入数据的大小如何，算法的执行时间都是固定的。

举例：

sum=sum+1;
sum=sum+2;
sum=sum+3;
sum=sum+4;

sum=sum+1;执行了4遍，即使重复了100次，也都是常数级，都用O(1)表示。

---

1.2.2. 线性阶 O(n)

线性阶表示执行的次数随着问题规模是线性变化的

线性阶（O(n)）表示算法的执行时间与输入数据的大小n成正比。换句话说，当输入数据的大小n增加时，算法的执行时间也会线性地增加。

举例：

• 使用for循环遍历数组：

int[] arr = {1, 2, 3, 4, 5};  
for(int i = 0; i < arr.length; i++){  
    System.out.println(arr[i]);  
}

这段代码会遍历数组arr并打印每个元素，所以它的执行次数与数组的长度成正比，是线性阶。

• 使用while循环遍历数组：

int i = 0;  
int[] arr = {1, 2, 3, 4, 5};  
while(i < arr.length){  
    System.out.println(arr[i]);  
    i++;  
}

这段代码也会遍历数组arr并打印每个元素，所以它的执行次数与数组的长度成正比，是线性阶。

• 使用递归函数计算阶乘：

public static int factorial(int n) {  
    if (n == 0) {  
        return 1;  
    } else {  
        return n * factorial(n - 1);  
    }  
}

这段代码使用递归函数计算给定数字的阶乘。虽然递归的次数与输入数据的大小n有关，但由于每次递归都会返回结果，所以整个递归过程的执行次数与n成正比，是线性阶。

---

1.2.3. 平方阶 (n2)

平方阶主要是双层循环嵌套。

int i,j;
for(i=0;i<n;i++){
 for(j=0;j<n;j++){
    //todo 时间复杂度为1的程序
    todo...
 }
}

上面的todo随着n是呈平方级别增加的，n是2，就执行4次，n是3就执行9次，所以是平方阶。

上面的例子可以变形为：

int i,j;
for(i=0;i<n;i++){
 for(j=i;j<n;j++){
    //todo 时间复杂度为1的程序
    todo 
 }
}

首先，外层循环会执行n次，这是很直观的，因为i从0到n-1，所以总共n次。

关键在内层循环。当我们看内层循环时，我们要注意j的起始值是i。这意味着，对于每一次外层循环的迭代，内层循环的次数都在减少。

例如：

• 当i=0时，j从0到n-1，所以内层循环n次。
• 当i=1时，j从1到n-1，所以内层循环n-1次。
• 以此类推...
• 当i=n-1时，j只从n-1到n-1，所以内层循环1次。

现在，我们要计算内层循环的总次数。这就像把上面列出的所有次数加起来：n + (n-1) + (n-2) + ... + 2 + 1。

这是一个等差数列的和。等差数列的和的公式是 n(n+1)/2。在这个情况下，它表示的是内层循环的总次数。

因此，整个嵌套循环的总执行次数就是 n(n+1)/2。当我们谈论时间复杂度时，我们通常关注最高阶的项，并忽略常数。

所以这里的时间复杂度也是O(n^2)。

---

1.2.4. 对数阶 O(logn)

二分查找，二叉树等问题经常会看到

其本质都可以简化成如下模型:

int count=1;
n=64
int items=0;
while(count<n){
   count=count*2;//todo注意看的是这行的执行次数与n的关系
   itmes++;
} 

count 代表当前的搜索范围的大小，每次迭代都会将 count 翻倍，直到 count 大于或等于 n。因此，每次迭代后，搜索范围会变成原来的两倍。

在上面的例子里，我们可以看一下todo的执行次数与count<n之间的关系:

todo执行次数 ?	第一次 ?	第二次 ?	第三次 ?	第四次 ?	第五次 ?	第六次 ?	第七次 ?
count ?	1 ?	2 ?	4 ?	8 ?	16 ?	32 ?	64

从上面可以看到，如果todo要执行第七次时，已经不满足count<n了，所以执行次数与n的关系正好是：2^x=n，也就是x=logn。

所以说，二分查找不过是每循环一次都是减半.所以todo的执行次数是logn次。

---

2. 最坏情况和平均情况

假设你有一组长度为n的随机数字，你希望通过一个算法快速找到其中的一个特定数字。在算法分析中，我们通常需要考虑三种情况：最好情况、最坏情况和平均情况。

1. 最好情况：你已经知道目标数字位于数组的开头位置。在这种情况下，你只需要比较一次就能找到目标数字。在算法分析中，最好情况的时间复杂度是O(1)，因为只需要进行一次比较。
2. 最坏情况：你不知道目标数字在数组中的位置，而且它实际上位于数组的末尾。在这种情况下，你需要遍历整个数组才能找到目标数字。在算法分析中，最坏情况的时间复杂度是O(n)，因为你需要进行n次比较才能找到目标数字。
3. 平均情况：你不知道目标数字在数组中的确切位置，但你有一些关于它可能位于数组中部的线索。因此，你需要在数组中进行一些比较才能找到目标数字。平均情况下，你可能需要进行大约n/2次比较才能找到目标数字。在算法分析中，平均情况的时间复杂度可能是O(n/2)，但实际上我们通常将其简化为O(n)，因为大O表示法关注的是数量级而不是常数因子。

为了更好地理解这个例子，可以将搜索算法想象成在一排有序的书架上查找一本书。最好情况就是你知道书名并且它就在你眼前；最坏情况就是你需要从书架的一端到另一端逐一查找；平均情况则是你可能需要查看书架上的几个位置才能找到你要的书。

在选择和使用算法时，我们需要权衡这些因素，以确保算法在实际应用中的效率和稳定性。

---

3. 空间复杂度

空间复杂度则是指一个算法执行过程中所需要消耗的内存资源数量。它反映了算法的存储开销，同样也是

以一定的数学模型来表示。一个算法的空间复杂度越低，则其所需要的内存空间就越少。