在Java中,while循环的时间复杂度是:

huangapple go评论92阅读模式
英文:

time complexity of while loop in java

问题

虽然我只使用了一个循环,但我不认为我的代码的时间复杂度是O(n)。
有人可以解释一下下面代码的时间复杂度吗?

  1. public class PatternPyramid {
  2. public static void main(String[] args) {
  3. int rows = 15;
  4. int i = 0;
  5. int j = 0;
  6. int k = rows - 1;
  7. while (i < rows) {
  8. if (j < k) {
  9. System.out.print(" ");
  10. j++;
  11. } else if (j < rows) {
  12. j++;
  13. System.out.print("* ");
  14. } else {
  15. j = 0;
  16. i++;
  17. k--;
  18. System.out.println();
  19. }
  20. }
  21. }
  22. }
英文:

Although I have used only one loop, I don't think the time complexity of my code is O(n).
Could anyone please explain me the time complexity of the code below.

  1. public class PatternPyramid {
  2. public static void main(String[] args) {
  3. int rows = 15;
  4. int i = 0;
  5. int j = 0;
  6. int k = rows - 1;
  7. while (i &lt; rows) {
  8. if (j &lt; k) {
  9. System.out.print(&quot; &quot;);
  10. j++;
  11. } else if (j &lt; rows) {
  12. j++;
  13. System.out.print(&quot;* &quot;);
  14. } else {
  15. j = 0;
  16. i++;
  17. k--;
  18. System.out.println();
  19. }
  20. }
  21. }
  22. }

答案1

得分: 1

The time complexity is O(n2), where n is the number of rows.

It requires n iterations to print each row of n characters. Furthermore, it requires n iterations to print each of the new lines.

Ergo, the time complexity is:

O(n * n + n)
= O(n2 + n)
= O(n2)

英文:

The time complexity is <code>O(n<sup>2</sup>)</code>, where n is the number of rows.

It requires n iterations to print each row of n characters. Furthermore, it requires n iterations to print each of the new lines.

Ergo, the time complexity is:

<code>O(n * n + n)</code><br/>
<code>= O(n<sup>2</sup> + n)</code><br/>
<code>= O(n<sup>2</sup>)</code><br/>

答案2

得分: 0

  1. for (int i = 0; i < rows; i++) {
  2. for (int j = i; j < rows; j++)
  3. System.out.print(" ");
  4. for (int k = 0; k <= i; k++)
  5. System.out.print("* ");
  6. System.out.println();
  7. }

Your code could be transformed into nested loops like this. The outer loop runs O(rows) times. The loop for spaces runs "rows - i" times for each iteration, and the loop for asterisks runs "i" times. Combining them results in the inner loops running "rows" times.

Thus, the total time complexity would be O(rows^2).

英文:
  1. for (int i=0; i&lt;rows; i++) {
  2. for(int j=i; j&lt;rows;j++)
  3. System.out.print(&quot; &quot;);
  4. for(int k=0; k&lt;=i; k++)
  5. System.out.print(&quot;* &quot;);
  6. System.out.println();
  7. }

Your code could be transformed into for loops like this, as it can be seen that outer loop run O(rows) times, and the loop for spaces runs rows-i times for each iteration whereas loop for asterisks run i times. Combining them would result in the inner loops running rows times.

Thus total time complexity would be O(rows^2)

huangapple
  • 本文由 发表于 2020年7月26日 02:51:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/63092263.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定