<form id="dlljd"></form>
        

        <address id="dlljd"><address id="dlljd"><listing id="dlljd"></listing></address></address>
        <em id="dlljd"><form id="dlljd"></form></em>
          
<address id="dlljd"></address>
            <noframes id="dlljd">
              


              
	
              
		
		聯系我們 - 廣告服務 - 聯系電話：
		
	
              

              

              
	
	
	
              
	
              

              


               您的當前位置： > 關注 >  > 正文
              


              
  
              
    
              
      
              分治思想的核心是什么？簡述遞歸和分治的關系
              
      
               來源：CSDN   時間：2023-03-17 10:25:11 
        
      
              
	  
      
	  
              
        
              分治顧名思義“分而治之”，英文的意思翻譯為“分割并征服”。
              分治思想，簡而言之就是將原問題分解成與“原問題相同但是規模更小”的子問題，并可以反復執行這個過程，使得問題規模減小到可以求解為止。
              1、快速排序算法

              (資料圖片僅供參考)
              2、快速傅里葉變換算法
              3、Karatsuba大數乘法算法
              問題：給定1000個數，從小到大進行排序。
              先選擇一個“標準”A，按照“比A小”和“比A大”將原來的數列分為兩類，這樣，只需要將兩個子序列分別排好序，然后再合并到一塊就ok了。
              直接做該運算，需要做平方級別的復數乘法，這樣的復雜度超級高！如何進行分解呢？
              首先，不可能像上邊排序算法一樣，找一個“標準數”，取前一半和后一半采樣點來做！
              問題：兩個很大的數相乘，如何更快的解決？
              兩個很大的數相乘，普通算法的時間復雜度為O(n^2)。
              首先，將n位大數x和y進行分解。
              然后，x·y就變成了下面這樣
              并且滿足
              所以，原來的大數乘法就變成了小數乘法！其實這位博士研究的算法不僅這里巧妙，而且還有一個小技巧！
              這樣的話，乘法又能變成加法了！計算復雜度又大大的降低了！
              第一：數學歸納是使用分治思想
              只要出現可以用數學歸納公式來表示的大規模問題，第一反應就應該想到分治算法，通過特定的函數參數安排，一定可以用同一個函數來表述不同規模的問題，套用遞歸結構，可迅速解決問題！
              第二：分治思想不一定使用遞歸結構
              遞歸結構是循環結構的一種，也是分治思想應用最多的一種程序結構，但是不一定要使用它！關鍵在于能夠寫出遞歸公式以及是否有必要使用遞歸算法。比如上邊提到的快速傅里葉變換算法，就沒有用到遞歸！
              三：分治思想的核心是“如何分”
              能夠把問題很棒的進行分解，也是一種能力和本事！也就是說把問題用分治法來進行解決，是算法的難點，也是重點！一方面需要經驗，另一方面也需要想象力！所以說呢？人生也是如此！不管遇到多大的苦難，我們需要在一次一次的鍛煉中進行學會分解苦難，才能夠大事化小，小事化了！
                    
              
      
               責任編輯： 
              
      
              
        
                
			        
              
      
              
	  
              
	  
		
              標簽：
		 
		
              
		
		
	  
              
    
      
      
      
              
        
               相關推薦： 
              
        
                
		        
              
      
              
	  
	  
      
              
        
               精彩放送： 
              
        
      
              
    
              
  
              
  
                      

                
    
    
    
  
    
              
      
               新聞聚焦 
              
      
    
              
	
  
              
  
               
              

              


               
  
Top


中文字幕在线观看亚洲日韩