英文:
time complexity of while loop in java
问题
虽然我只使用了一个循环，但我不认为我的代码的时间复杂度是O(n)。
有人可以解释一下下面代码的时间复杂度吗？
public class PatternPyramid {
public static void main(String[] args) {
int rows = 15;
int i = 0;
int j = 0;
int k = rows - 1;
while (i < rows) {
if (j < k) {
System.out.print(" ");
j++;
} else if (j < rows) {
j++;
System.out.print("* ");
} else {
j = 0;
i++;
k--;
System.out.println();
}
}
}
}
英文:
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.
public class PatternPyramid {
public static void main(String[] args) {
int rows = 15;
int i = 0;
int j = 0;
int k = rows - 1;
while (i < rows) {
if (j < k) {
System.out.print(" ");
j++;
} else if (j < rows) {
j++;
System.out.print("* ");
} else {
j = 0;
i++;
k--;
System.out.println();
}
}
}
}
答案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
for (int i = 0; i < rows; i++) {
for (int j = i; j < rows; j++)
System.out.print(" ");
for (int k = 0; k <= i; k++)
System.out.print("* ");
System.out.println();
}
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).
英文:
for (int i=0; i<rows; i++) {
for(int j=i; j<rows;j++)
System.out.print(" ");
for(int k=0; k<=i; k++)
System.out.print("* ");
System.out.println();
}
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)
专注分享java语言的经验与见解，让所有开发者获益！
评论