java练习本(2019-08-18)

昨日翻译

“Never be jealous again. Never doubt that I love you more than the world. More than myself.”

—— Alexandre Dumas

“别再嫉妒了。不要怀疑我爱你胜过爱世界。不仅仅是我自己。”

——大仲马

今日名言

“Though I know he loves me, tonight my heart is sad; his kiss was not so wonderful as all the dreams I had.”

—— Sara Teasdale

2019.08.16问题及解析

题目

void fun(int n) {
   for (int i = 0; i < n; i++) {
       for (int j = i; j < n; j++) {
           System.out.print("Hello World！");
      }
  }
}

上述代码的时间复杂度是？

A.O(n)

B.O(n^2)

C.O(1)

D.O(logn)

答案与解析

1.相关知识

时间复杂度用来描述算法的运行时间，通常用大O表示

常见的数量级有1，n，logn，n^2等

我们可以根据算法的时间复杂度来推算算法的运行效率，从而选择合适的算法。

2.答案解析

System.out.print("Hello World！");

我们可以视一个语句的时间频度是1，那么执行这个语句它的时间复杂度其实就是O（1）

那么我们执行这个语句n次呢，相当于就是需要花费n倍的1时间来执行它也就是

for (int j = i; j < n; j++) { System.out.print("Hello World！"); }

因此它的时间复杂度就是O（n）

再来看题目，内存循环的次数，开始是j=0,j<n,要循环j次

之后j=1,j<n，要循环j-1次

......

最后j=n-1,j<n，循环1次

总共1+2+...+n=n(n+1)/2次=n^2/2+n/2

计算时间复杂度时我们通常用最高项来代表时间复杂度

最高项为n^2/2，因此最终的时间复杂度为O（n^2）

答案选B。

2019.08.18问题

题目分类

数据结构——时间复杂度

题目

void fun(int n) {
       for (int i = 2; i < n; i++) {
           i *= 2;
           System.out.println("i: " + i);
      }
}

上述代码的时间复杂度是？

A.O(n)

B.O(n^2)

C.O(1)

D.O(logn)

END