JAVA数据结构与算法的学习——求和

阳光穿透心脏的1/2处 2022-03-25 08:58 242阅读 0赞

在数据结构与算法中，我们来讲讲求和这个经典问题，不对之处还请各位不吝赐教。  
求：**1+2+3+…+100的和**  
想必大家都会想这个太简单的了吧，用一个`for循环`不就得了，的确是可以这样但是你有想过这样做的复杂度是多少吗？我们算法的精湛就是要复杂度越小越好，资源利用的越少越好  
先上**for循环**的代码：

//求1+2+3+....+100的和
    public class Main1 {
    
    	public static void main(String[] args) {
    		int n=100,sum=0;
    		for(int i=1;i<=n;i++) {
    			sum+=i;
    		}
    		System.out.println(sum);
    	}
    }

如果面试你是这么写的，你已经被**PASS**掉了，为什么呢？请接着往下看

对问题**进行分析**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70][]  
你应该能找出其中的**规律**，也就是我们初高中的**公式**，所以我们应该这么写：

//求1+2+3+....+100的和
    public class Main2 {
    
    	public static void main(String[] args) {
    		int n=100,sum=0;
    		sum=(1+n)*n/2;
    		System.out.println(sum);
    	}
    
    }

答案应该是这样，这两中算法的**好坏**应该用什么来衡量呢？  
肯定是上面所提到的**复杂度**啦，不懂的小伙伴可以百度或者翻阅书籍，这是一个很重要的概念！  
对比两种算法：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 1][]  
资源图：![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 2][]  
X轴是内容，Y轴是资源，我们可以看出，n和1中资源使用的差别，可能这个例子还不太明显，但你可以发现**n！和2的n次方与n，1对比**，可以说是**天差地别**的！

由分析得，显然是第二种算法好，复杂度低，算法是特别重要的，因为在一些应用的场景，例如一些高并发，如果使用到的算法是很高复杂度的，那么服务器反应很慢或者很快就会宕机，所以一定要认识算法的重要性，掌握好算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70]: /images/20220325/d3e3335305214d37a64386372c36f014.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 1]: /images/20220325/6f5502ab6bad42ab86a68727a4151b15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70 2]: /images/20220325/e5d7fc8aef9e4734a57b3aecd8985ed5.png