roimin1
@roimin1

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

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

1Answer

もっと詳しく説明できる方がいらっしゃると思いますが、
O(N)厳密なステップ数ということではなくて、『 N に比例した計算量』であるという意味です。
掲示されていたソースコードですと、ループは一重でループ回数は n のため、計算量O(n) で正しい理解だと思います。

以下の記事に詳しく説明されていました。

1Like

Comments

  1. @roimin1

    Questioner

    O(n)の定義と、計算量を教えて下さりありがとうございます!
    記事も拝見します!

Your answer might help someone💌