練習時間復雜度
void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
System.out.println(arr[j]);
}
}
}
O(N^2)
not because there is two for loop
void print(int[] arrA, int[] arrB) {
for (int i = 0; i < arrA.length; i++) {
for (int j = 0; j < arrB.length; j++) {
if (arrA[i] < arrB[j]) {
System.out.println(arrA[i] + "," + arrB[j]);
}
}
}
}
O(N × M)
N = arrA.length, M = arrB.length
void print(int[] arrA, int[] arrB) {
for (int i = 0; i < arrA.length; i++) {
for (int j = 0; j < arrB.length; j++) {
for (int k = 0; k < 10000000; k++) {
System.out.println(arrA[i] + "," + arrB[j]);
}
}
}
}
O(N × M)
N = arrA.length, M = arrB.length
// Node { Node right; Node left; int value }
int sum(Node node) {
if (node == null) {
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
O(N)
N = number of nodes
boolean isPrime(int n) {
for (int x = 2; x * x < n; x++) {
if (n % x == 0) {
return false;
}
}
return true;
}
O(√N)
int factorial(int n) {
if (n < 0) {
return -1;
} else if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
O(N)
