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

2023-12-15 19:39:56

目录

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. 空间复杂度

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

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

文章来源:https://blog.csdn.net/Sakurapaid/article/details/135023763
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。