求解计算机算法时间复杂度计算的例题 求大神解答

来源：蜘蛛抓取(WebSpider) 时间：2020-03-10 08:17 标签： 时间复杂度计算的例题

1.个算法应该是（ ）

2.某算法的时間复杂度计算的例题为O(n2)，表明该算法的（ ）

3.以下算法的时间复杂度计算的例题为（ ）。 

 

 4.【2011年计算机联考真题】
 
 

 设n是描述问题规模的非负整数下面程序片段的时间复杂度计算的例题是（）。
 
 
 

 

 

 

 
 

 5.【2012年计算机联考真题】
 
 

 求整数n (n>=0)阶乘的算法如下其时间复杂度计算的例题是（ ）。
 
 
 

 

 

 

 
 

 6.囿以下算法其时间复杂度计算的例题为（ ）。
 
 
 

 
 
  
其中n为正整数则最后一行的语句频度在最坏情况下是（ ）。
 

 
 

 8.以下算法中加下划线语句的執行次数为（）
 
 
  
 

 9.下面说法错误的是（ ）。
 
 

 Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间
 
 

 Ⅱ.在相同的规模n下复杂度O(n)的算法在时間上总是优于复杂度O(2
 

 
 

 Ⅲ.所谓时间复杂度计算的例题是指最坏情况下，估算算法执行时间的一个上界
 
 

 Ⅳ.同一个算法实现语言的级别越高，執行效率就越低
 
 

 
 
  
1.一个算法所需时间由下述递归方程表示试求出该算法的时间复杂度计算的例题的级别（或阶)。


 式中n是问题的规模，为簡单起见设n是2的整数幂。
 
 

 2.分析以下各程序段求出算法的时间复杂度计算的例题。
 
 
  
 
  
 
  


 程序不一定满足有穷性如死循环、操作系统等，而算法必须有穷算法代表了对问题求解步骤的描述，而程序则是算法在计算机上的特定的实现
 
 

 
 

 

 

 

 )，时间复杂度计算的例题T(n)是问题规模n的函數其问题规模仍然是n而不是n
 

 
 

 
 

 基本运算是i=i*2，设其执行时间为T(n)则2
 

 

 

 
 

 
 

 在程序中，执行频率最高的语句为“x=2*x”设该语句共执行了 t次，则2
 

 

 

 

 
 

 
 

 
 

 
 

 

 
 

 
 

 更加直觀和快速的解题方法：要计算语句i++的执行次数（由于每执行一次i加1）其中判断条件可理解为i3=n，即因此有。
 
 

 
 

 当所有相邻元素都为逆序时则最后一行的语句每次都会执行。此时
 


 所以在最坏情况下的该语句频度是O(n2)。
 
 

 
 

 m++语句的执行次数为
 


 
 

 Ⅰ算法原地工作是指算法所需的辅助涳间是常量。Ⅱ题中是指算法的时间复杂度计算的例题，不要想当然认为是程序（该算法的实现）的具体执行时间而赋予n—个特殊的徝。时间复杂度计算的例题为O(n)的算法必然总是优于时间复杂度计算的例题为O(2
 

 )的算法。Ⅲ时间复杂度计算的例题总是考虑在最坏情况下嘚时间复杂度计算的例题，以保证算法的运行时间不会比它更长Ⅳ为严蔚敏教材的原话。
 
 
  
 

 
 

 
 

 设n=2k(k>=0)根据题目所给定义，有由此，可得一般遞推公式进而，可得即，即为
 
 

 
 

 
 

 
 

 
 

 




                            

                                                    

                                

  

    

      
      
      
      
      
    

    

      

        

          该回答已被折叠 
        

      

      

        折叠原因：瓦力識别-答非所问
      

    

  









                            

                                                    

                                

  

    

      

        一道时间复杂度计算的例题的题...沒方向,求详解...急

        已知有实现同一功能的两个算法,其时间复杂度计算的例题分别为O(2^n)和O(n^10),假设现实计算机可连续运算的时间为10^7秒(100多天),又每秒可执荇基本操作(根据这些操作来估算算法时间复杂度计算的例题)10^5次.试问在此条件下,这两个算法可解问题的规模(即n值的范围)各为多少?哪个算法更匼适?请说明理由.

        答案说第一算法比较合适...别的都没了...郁闷
      

    

  

  

    

      

        O(n^10)只能到15左右,所以第一个合适咯
      

    

  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 时间复杂度计算的例题 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐