Javaのコードの計算ステップの数え方を知りたい
解決したいこと
言語:java
アルゴリズムの勉強中です。
O記法の計算方法の初期の初期で躓いています。
以下のコードが、
O記法でなぜ、どのようなことがあってO(n)と判断されるかが知りたいです。
コードは素数判定のものを使用しています
該当するソースコード
//受け取った値が素数ならTrue、素数でないならFalseを返す関数を実装する
public class Main {
// 整数を受け取り、素数かどうかを判定する関数
static boolean primalityTest(int n) {
//与えられた値(n)が1以上であるかどうか判定する
if (n==1){//1回実行?
return false;//1は素数ではないから。nは入力される値。
}
//2以上n未満の整数でnを割り切るものが存在しないのがTrue
//受け取った値が素数ならtrue、素数でないならfalseを返す関数を実装する
for (int i=2;i<n;i++){
if (n%i==0){
return false;//nの回数分だけ判定するのでn回実行?
}
}
return true;//1回実行
}
public static void main(String[] args) {
int n = 1;//1回実行
boolean isPrime = primalityTest(n);//1回実行
if(isPrime){
System.out.println(n + "は素数");//1回実行
}else{
System.out.println(n + "は素数ではない");//1回実行
}
}
}
自分で試したこと
計算ステップとは何かを調べた
自分で調べた結果、コード内に//1回?
というような回数の数え方をしています。そもそもあっているのかどうかも分かりません。
調べた知識を使って数えた結果基本演算(計算ステップ)はn+6回で、O(n)となりました。
この考え方であっているのでしょうか。
0