小编war*_*tar的帖子

我有一系列问题需要反馈和答案.我将评论我的想法,这不是一项家庭作业,而是为我的考试做准备.

我的主要问题是确定不同情况下循环的迭代.怎么会尝试解决这个问题？

评估运行时间.

Q2.

 for(int i =0 ; i < =n ; i++) // runs n times
   for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
      if (j % i == 0)
         for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
            sum++;

正确答案:N×N2×N = O(N ^ 4)

对于以下问题,我没有正确的答案.

Q3.一个)

     int x=0; //constant
     for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
         x=x+2*i;

我的答案:O(n)

b)为简单起见,假设n = 3 …

下面的方法反转了具有n个元素的双向链表.我不明白这是如何工作的.我添加了评论,如果我错了,请纠正我.我不确定遍历过程是如何工作的.

 public void reverseDLL( ) {
   Node temp=head; //swap head and tail
   head=tail; // head now points to tail
   tail=temp; //tail points to head
    //traverse the list swapping prev and next fields of each node
  Node p=head; //create a node and point to head

  while(p!=null) //while p does not equal null
    { //swap prev and next of current node
      temp=p.next; // p.next does that not equal null? confusing.
      p.next=p.prev; //this line makes sense since you have to reverse the link …

请考虑以下Java方法:

   public static void f(int n) {
    if (n<=1) { 
       System.out.print(n) ; 
       return; 
   }else {
       f(n/2) ;
       System.out.print(n);
       f(n/2);
    }
 } // end of method

问题3.设S(n)表示f(n)的空间复杂度.以下哪项陈述是正确的？

• 答:S(n)=(2n)
• B:S(n)=(n)
• C:S(n)=(log n)< - 正确答案,有谁知道为什么？
• D:以上都不是

int lf = ((t.left==null) = (t.right==null)) ? 1:0;

如果较大括号中的语句为真,则返回1,但在中间,是否为lefT分配正确的值？