今日は、テスト返しの残り時間で、4年の情報構造論で、リスト構造などの内容を進める前に、3年プログラミング応用でクラスなどに自信がない人向けの簡単レクチャ。

クラスは、データ構造と手続き

例えば、名前と年齢のデータをクラスで扱うのであれば、以下のようなコードが基本となるだろう。

import java.util.*;

class NameAge {
    String name ;          // インスタンス変数
    int    age ;           // インスタンス変数
    static int count = 0 ; // クラス変数
    // コンストラクタ
    NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

実行結果
tsaitoh,59
member = 1
age = 59
tomoko,48
member = 2

クラスとは、データ構造(オブジェクト)とそのデータ構造を扱うための関数(メソッド)をまとめて扱う。

クラス NameAge の中で宣言されている、NameAge() の関数は、オブジェクトを初期化するための関数(メソッド)であり、特にコンストラクタと呼ばれる。

実際にデータを保存するための tsaitoh や tomoko とよばれる変数に NameAge オブジェクトの実体を作る時には 「new クラス名」 とやることで、初期化ができる。

イメージでは、下図のようなデータ構造ができあがる。

でも、年齢の覚え方は、将来的に誕生日を覚えるように変化するかもしれない。この際に、Main 関数の中で age を使うと後で混乱の元になるかもしれない。こういう時は、NameAge クラス以外では中身を勝手に使わせないために、インスタンス変数などに public / private といったアクセス制限を加える。

import java.util.*;
class NameAge {
    private String name ;          // インスタンス変数
    private int    age ;           // インスタンス変数
    public  static int count = 0 ; // クラス変数
    // コンストラクタ
    public  NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    public void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ここがエラーになる。NameAge::age は private 
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

クラス自体も、public class NameAge … のように宣言することもあるが、public なクラスは 1つ の *.java ファイルの中に1つしか書けないというルールがあるので要注意。

中間試験問題の回答

import java.util.*;
import java.util.* ;

class Item {
    int    id ;
    String name ;
    int    price ;
    Item( int i , String n , int p ) {
        this.id    = i ;
        this.name  = n ;
        this.price = p ;
    }
} ;

class Buy {
    int    id ;
    int    count ;
    Buy( int i , int n ) {
        this.id    = i ;
        this.count = n ;
    }
} ;

public class Main {
    static Item[] item_list = {
        new Item( 1010 , "orange" ,      50 ) ,
        new Item( 1020 , "apple" ,      100 ) ,
        new Item( 1022 , "pineapple" , 1000 ) ,
    } ;
    static Buy[] buy_list = {
        new Buy( 1010 , 5 ) ,
        new Buy( 1020 , 3 ) ,
        new Buy( 1022 , 1 ) ,
    } ;
    public static void main( String[] args ) {
        System.out.println( total_price( item_list , buy_list ) ) ;
    }
    static int total_price( Item[] i_list , Buy[] b_list ) {
        int sum = 0 ;
        for( Item item : i_list )
            for( Buy buy : b_list )
                if ( item.id == buy.id )
                    sum += item.price * buy.count ;
        return sum ;
    }
    // static int total_price( Item[] i_list , Buy[] b_list ) {
    //     int sum = 0 ;
    //     for( int i = 0 ; i < i_list.length ; i++ )
    //         for( int j = 0 ; j < b_list.length ; j++ )
    //             if ( i_list[ i ].id == b_list[ j ].id )
    //                 sum += i_list[ i ].price * b_list[ j ].count ;
    //     return sum ;
    // }
}

練習問題

科目(Subject)と学生(Student)の情報があり、科目を受講した成績(Result)で成績を管理している。
このデータを管理するためのクラスを宣言し、下に示すような出力が得られるプログラムを作成せよ。

今回の中間テストで成績が悪かった人は、テスト前に示したレポート課題ではなく下記の課題で提出してよいこととする。

科目: Subject
id    name       teacher   // Subject[] subject_table = {
10010 情報構造論 t-saitoh   //    new Subject( 10010 , "情報構造論" , "t-saitoh" ) ,
10020 電気磁気学 takaku     //    new Subject( ....
10030 電気回路   komatsu    // } ;

成績: Result
s_id  id         point      // Result[] result_table = {
16213 10020      83         //    new Result( 16213 , 10020 , 83 ) ,
18348 10010      95         //    new Result( ...
17101 10030      64         // } ;
16213 10010      89

学生: Student
s_id  name       age        // Student[] student_table = {
16213 斉藤太郎   18          //    new Student( 16213 , "斉藤太郎" , 18 ) ,
17101 山田次郎   19          //    new Student( ...
18348 渡辺花子   18          // } ;

以下のようなデータが出力されること
斉藤太郎 電気磁気学 83
渡辺花子 情報構造論 95
山田次郎 電気回路   64
斉藤太郎 情報構造論 89

C言語でのポインター

#include <stdio.h>

int main() {
    int  x  = 123 ; //                             px [ 〇 ]
    int* px ;       // px はポインタ                      ↓
    px = &x ;       // x の変数の番地を px に代入      x [ 123 ]
    *px = 321 ;     // px の指し示す場所に 321 を代入
    printf( "%d\n" , x ) ; // 321 を出力
    return 0 ;
}

値渡し(pass by value)

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
   return 0 ;
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか？

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
   return 0 ;
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
int main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
   return 0 ;
}

ポインタ渡し(pass by pointer)

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
int main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
   return 0 ;   // さらに125と増える
}

ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。C++では、ポインタ渡しを極力使わないようにするために、参照渡しを利用する。ただし、ポインタ渡しも参照渡しも、機械語レベルでは同じ処理にすぎない。

参照渡し(pass by reference)

// ポインタ渡しのプログラム
void foo( int& x ) {  // xは参照
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後 main::a は 124 に増えている。
   foo( a ) ;  // 124
   return 0 ;  // さらに125と増える。
}

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式) と p[ 整数式 ] は同じ意味 (参照”悪趣味なプログラム”)

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

ポインタと文字列処理

#include <stdio.h>

void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '
#include <stdio.h>

void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

int main(void){
    char str[ 20 ] ;

    my_tolower( str , "AaBcDeF Hoge" ) ;
    printf( "%s\n" , str ) ;
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '
#include <stdio.h>

void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

int main(void){
    char str[ 20 ] ;

    my_tolower( str , "AaBcDeF Hoge" ) ;
    printf( "%s\n" , str ) ;
    return 0 ;
}
' ;
}

int main(void){
    char str[ 20 ] ;

    my_tolower( str , "AaBcDeF Hoge" ) ;
    printf( "%s\n" , str ) ;
    return 0 ;
}

• my-tolower-1

間違ったプログラム

C言語の面倒な点は、データがどのように格納されるのかを考えないと正しく動かない所であろう。

下記のプログラムの問題点がわかるだろうか？

#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '
#include <stdio.h>

// 前述の my_tolower と同じ
void my_tolower( char d[] , char s[] ) {
    int i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            d[i] = s[i] - 'A' + 'a' ;
        else
            d[i] = s[i] ;
    d[i] = '\0' ;
}

// 引数に副作用のある my_tolower
char* my_tolower_1( char s[] ) {
    for( int i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            s[i] = s[i] - 'A' + 'a' ;
    return s ;
}

// 局所変数のメモリを帰してはダメ
char* my_tolower_2( char s[] ) {
    char str[ 20 ] ;
    int  i ;
    for( i = 0 ; s[i] != '\0' ; i++ )
        if ( 'A' <= s[i] && s[i] <= 'Z' )
            str[i] = s[i] - 'A' + 'a' ;
        else
            str[i] = s[i] ;
    str[i] = '\0' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}
' ;
    // printf( "in my_tolower_2 : %s\n" , str ) ;
    return str ;    
}

int main(void) {
    char str[ 20 ] = "Hoge" ; ;

    // case-1
    char* ptr ;
    my_tolower( ptr , "Piyo" ) ; // Illegal instruction (core dumped)

    // case-2
    printf( "%s\n" , my_tolower_1( str ) ) ;
    printf( "%s\n" , my_tolower_1( "Fuga" ) ) ; // 小文字にならない

    // csse-3
    printf( "%s\n" , my_tolower_2( "foo" ) ) ;  // ゴミが表示される
    return 0 ;
}

• my_tolower-2

ポインタインクリメントと式

C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。

// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '\0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '\0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}
' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '\0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '\0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}
' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}

しかし、この strcpy は、ポインタを使って書くと以下のように書ける。

// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
   *p = '\0' ;
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )   // while( *p++ = *q++ ) ; でも良い
      ;
}

Javaでの引数に対する副作用

Javaでのプログラムにおいて、下記のように関数に引数でデータが渡された場合、呼び出し元の変数が変化する／変化しないの違いが分かるであろうか？

import java.util.*;

class A {
    private int a ;
    public A( int x ) { a = x ; }
    public void set( int x ) { a = x ; }
    public int get() { return a ; }
}

public class Main {
    public static void foo( int x , Integer y , String s , int z[] , A a ) {
        x = 12345 ;        // プリミティブな引数の書き換え
        y = 23456 ;        // イミュータブルな引数の書き換え
        s = "hoge" ;
        z[0] = 34567 ;     // 参照で渡されたオブジェクトの書き換え
        a.set( 45678 ) ;
    }
    public static void main(String[] args) throws Exception {
        int     mx = 11111 ;        // プリミティブなデータ
        Integer my = 22222 ;        // イミュータブルなオブジェクト
        String  ms = "aaa" ;
        int     mz[] = { 33333 } ;  // それ以外のオブジェクト
        A       ma = new A( 44444 ) ;

        foo( mx , my , ms , mz , ma ) ;

        System.out.println( "mx="+mx+",my="+my+",ms="+ms+",mz[0]="+mz[0]+",ma="+ma.get() );
    }
}

• Paiza.ioのプログラム

上記のプログラムでは、foo() の第1引数 mx は、プリミティブ型なので関数の引数に渡される際には、コピーが生成されて渡されるため、呼び出し元の変数 mx の値は変化していない。

Javaでは、プリミティブ型以外のデータは、ヒープ領域に実体が保存され、そのデータの場所(ポインタ)によって管理される。

しかし、Integer型のオブジェクト my や、String型のオブジェクト ms は、参照(データの場所)が渡されるが、イミュータブルな(変更できない)オブジェクトなので、値の代入が発生すると新しいオブジェクトが生成され、そのアドレスが参照を保存している変数(ポインタ)に代入される。このため、呼び出し元の my や ms は値が変化しない。

これに対し、配列 mz や クラスオブジェクト ma は、オブジェクトの中身を関数 foo で値を変更すると、呼び出し元の変数の内容が変更される。こういった関数やメソッドの呼び出しによって、呼び出し元の値が変化することは「副作用」と呼ばれる。

こういった参照のメカニズムは、データの管理の仕方を正しく理解する必要があることから、もっと原始的な C 言語にて理解を目指す。

C言語の基礎

#include <stdio.h>

int main() {
   int n ;
   scanf( "%d" , &n ) ;  // 標準入力から整数をnに保存
   int m = 1 ;
   for( int i = 1 ; i <= n ; i++ )
      m *= i ;
   printf( "%d! = %d\n" , n , m ) ; // 
   return 0 ;
}

printf の最初の引数は、表示する際のフォーマットであり、%d の部分には対応する引数の値に置き換えて表示される。

   型                |   基数             |   型            |   表示方式
  long int      %ld  |  10進数        %d  |  double    %lf  |  固定小数点表示 %f  12.34
  int           %d   |  16進数        %x  |  float     %f   |  指数小数点表示 %e  1.234e+1
  short int     %hd  |   8進数        %o  |                 |  固定/指数自動  %g
  char          %c   |                    |  printf( "%5.2f" , 1.2345 ) ; □1.23
  char[], char* %s   |                    |

// Compile by C++
#include <stdio.h>

int main(void) {
    long int  x = 123456789L ;
    int       y = 1234567 ;
    short int z = 32767 ;
    printf( "%ld %d %hd\n" , x , y , z ) ;
    //      123456789 1234567 32767
    printf( "%d %x %o\n" , 0x1000 , 32767 , 32767 ) ;
    //      4096 7fff 77777
  
    double    p = 123.45678L ;
    float     q = 12.345 ;

    printf( "%lf %f\n" , p , q ) ;
    //      123.456780 12.345000
    printf( "(%lf) (%8.3lf) (%le)\n" , p , p , p ) ;
    //      (123.456780) ( 123.457) (1.234568e+02)   

    char      c = 0x41 ;
    char      s[] = "ABCDE" ;
    char      t[] = { 0x41 , 0x42 , 0x43 , 0x0 } ; // C言語の文字列の末尾には'
// Compile by C++
#include <stdio.h>

int main(void) {
    long int  x = 123456789L ;
    int       y = 1234567 ;
    short int z = 32767 ;
    printf( "%ld %d %hd\n" , x , y , z ) ;
    //      123456789 1234567 32767
    printf( "%d %x %o\n" , 0x1000 , 32767 , 32767 ) ;
    //      4096 7fff 77777
  
    double    p = 123.45678L ;
    float     q = 12.345 ;

    printf( "%lf %f\n" , p , q ) ;
    //      123.456780 12.345000
    printf( "(%lf) (%8.3lf) (%le)\n" , p , p , p ) ;
    //      (123.456780) ( 123.457) (1.234568e+02)   

    char      c = 0x41 ;
    char      s[] = "ABCDE" ;
    char      t[] = { 0x41 , 0x42 , 0x43 , 0x0 } ; // C言語の文字列の末尾には'\0'が必要

    printf( "(%c) (%s) (%s)\n" , c , s , t ) ;   
    //       (A) (ABCDE) (ABC)
    return 0 ;
}
'が必要

    printf( "(%c) (%s) (%s)\n" , c , s , t ) ;   
    //       (A) (ABCDE) (ABC)
    return 0 ;
}

C言語でのポインター

#include <stdio.h>

int main() {
    int  x  = 123 ; //                             px [ 〇 ]
    int* px ;       // px はポインタ                      ↓
    px = &x ;       // x の変数の番地を px に代入      x [ 123 ]
    *px = 321 ;     // px の指し示す場所に 321 を代入
    printf( "%d\n" , x ) ; // 321 を出力
    return 0 ;
}

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式) と p[ 整数式 ] は同じ意味 (参照”悪趣味なプログラム”)

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

ポインタインクリメントと式

C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。

// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
   int i ;
   for( i = 0 ; s[ i ] != '\0' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '¥0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}
' ; i++ )
      d[ i ] = s[ i ] ;
   d[ i ] = '¥0' ;
}

int main() {
   char a[] = "abcde" ;
   char b[ 10 ] ;
   strcpy( b , a ) ;
   printf( "%s\n" , b ) ;
   return 0 ;
}

しかし、この strcpy は、ポインタを使って書くと以下のように書ける。

// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
   while( *q != '\0' ) {
      *p = *q ;
      p++ ;
      q++ ;
   }
   *p = '\0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
   while( *q != '\0' )
      *p++ = *q++ ;    // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
   while( (*p++ = *q++) != '\0' )   // while( *p++ = *q++ ) ; でも良い
      ;
}
' )   // while( *p++ = *q++ ) ; でも良い
      ;
}

前回の講義で説明できなかった、オーダーの問題の解説

練習問題

1. の処理時間を要するアルゴリズム(データ件数が変わっても処理時間は一定)を、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
2. ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか？
3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
   (ヒント: ロピタルの定理)

• 1は、O(1)。
  • 誤答の例：O(0)と書いちゃうと、T(N)=T_α×0=0になってしまう。
  • 事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
• 2は、N→∞において、N² ≪ 2^Nなので、O(2^N) 。厳密に回答するなら、練習問題3と同様の証明が必要。
• 3の解説

再帰呼び出しの基本

次に、再帰呼び出しを含むような処理の処理時間見積もりについて解説をおこなう。そのまえに、再帰呼出しと簡単な処理の例を説明する。

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

階乗 fact(N) を求める処理は、以下の様に再帰が進む。(N=5の場合)

また、フィボナッチ数列 fib(N) を求める処理は以下の様に再帰が進む。(N=5の場合)

再帰呼び出しの処理時間

次に、この再帰処理の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=T_a で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(T_b)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 T(N)=T_b=T(N-1)で表せる。

} 再帰方程式

このような、式の定義自体を再帰を使って表した式は再帰方程式(漸化式)と呼ばれる。これを以下のような代入の繰り返しによって解けば、一般式  が得られる。

T(1)=T_a
T(2)=T_b+T(1)=T_b+T_a
T(3)=T_b+T(2)=2×T_b+T_a
:
T(N)=T_b+T(N-1)=T_b + (N-2)×T_b+T_a

一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。

再帰を含む一般的なプログラム例

ここまでのfact()やpyra()のような処理の再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で表現し、処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？

// 分割統治法による配列合計

#include <stdio.h>

int sum( int a[] , int L , int R ) { // 非末尾再帰
    // L : 左端のデータ
    // R : 右端のデータが入っているの場所+1
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    int array[ 8 ] = {
    // L=0  1   2   3   4   5   6   7   R=8
        3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
    } ;
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

// 分割統治法による配列合計

import java.util.*;

public class Main {
    static int sum( int a[] , int L , int R ) { // 非末尾再帰
        // L : 左端のデータ
        // R : 右端のデータが入っているの場所+1
        if ( R - L == 1 ) {
            return a[ L ] ;
        } else {
            int M = (L + R) / 2 ;
            return sum( a , L , M ) + sum( a , M , R ) ;
        }
    }
    public static void main(String[] args) throws Exception {
        int array[] = {
        // L=0  1   2   3   4   5   6   7  R=8  
            3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
        } ;
        System.out.println( sum( array , 0 , array.length ) );
    }
}

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端(左端のデータのある場所)・右端(右端のデータのある場所+1)を表している。そして、再帰のたびに２つに分割して解いている。

このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。

このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間T_s(N)は次の再帰方程式で表せる。

   ← T_β + (L〜M)の処理時間 + (M〜R)の処理時間

これを代入の繰り返しで解いていくと、

ということで、このプログラムの処理時間は、 で表せる。

ハノイの塔

ここまでは、簡単な再帰呼び出しのプログラムを例にして再帰方程式などの説明を行った。次に「ハノイの塔」の処理時間を例題に、プログラムの処理時間について分析を行う。

ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。

 … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
　… ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想①が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

　… ③より
 … ①を代入
      … ①のの場合

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

また、ハノイの塔の処理時間は、で表せる。

単純サーチの処理時間

ここで、プログラムの実行時間を細かく分析してみる。

// ((case-1))
// 単純サーチ O(N)
#include <stdio.h>

int main() {
    int a[ 10 ] = {
        12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
    } ;
    int N = 10 ;  // 実際のデータ数(Nとする)
    int key = 21 ;   // 探すデータ
    for( int i = 0 ; i < N ; i++ )
        if ( a[i] == key )
            break ;
    return 0 ;
}

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        int a[] = {
            12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
        } ;
        int N = a.length ;
        int key = 21 ;
        for( int i = 0 ; i < N ; i++ )
            if( a[i] == key )
                break ;
    }
}

例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その１つ１つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を ,,, とする。

この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。

ここで例題

この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか？

感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、T_β,T_α は何秒だったのだろうか？ 上記のT(N)=T_α+N ✕ T_β に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。

ここで一番のポイントは、データ処理では N が小さな値の場合(データ件数が少ない状態)はあまり考えない。N が巨大な値であれば、T_αは、1000T_βに比べれば微々たる値という点である。よって

で考えれば良い。これであれば、T(1000)=5μ秒=T_β×1000 よって、T_β=5n秒となる。この結果、T(10000)=T_β×10000=50μ秒 となる。

2分探索法と処理時間

次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。データはあらかじめ昇順に並べておくことで、一度の比較で対象件数を減らすことで高速に探すことができる。

下記プログラムを読む場合の注意点：

• Lは、探索範囲の一番左端のデータのある場所。
• Rは、探索範囲の一番右端のデータのある場所 + 1

// ((case-2))
// 2分探索法 O(log N)
#include <stdio.h>

int main() {
    int a[] = {
        9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
    } ;
    int L =  0 ; // L : 左端のデータの場所
    int R = 10 ; // R : 右端のデータの場所+1 
    while( L != R ) {
        int M = (L + R) / 2 ;
        if ( a[M] == key )
            break ;
        else if ( a[M] < key )
            L = M + 1 ;
        else
            R = M ;
    }
    return 0 ;
}

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int a[] = {
            9 , 12 , 21 , 29 , 35 , 59 , 61 , 64 , 73 , 83
        } ;
        int L = 0 ;        // L : 左端のデータの場所
        int R = a.length ; // R : 右端のデータの場所+1
        int key = 73 ;
        while( L != R ) {
            int M = (L + R) / 2 ;
            if ( a[M] == key )
                break ;
            else if ( a[M] < key )
                L = M + 1 ;
            else
                R = M ;
        }
    }
}

このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。

    …両辺のlogをとる

2分探索は、繰り返し処理であるから、処理時間は、

  … (Mはループ回数)

ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式 ()で係数が出てくるが、これはT_βに含めて考えればいい。

単純なソート(選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。

// ((case-3))
// 選択法 O(N^2)
#include <stdio.h>

int main() {
    int a[] = {
        12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
    } ;
    int size = 10 ;
    for( int i = 0 ; i < size - 1 ; i++ ) {
        int tmp ;
        // i..size-1 の範囲で一番大きいデータの場所を探す
        int m = i ;
        for( int j = i + 1 ; j < size ; j++ ) {
            if ( a[j] > a[m] )
                m = j ;
        }
        // 一番大きいデータを先頭に移動
        tmp = a[i] ;
        a[i] = a[m] ;
        a[m] = tmp ;
    }
    return 0 ;
}

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        int a[] = {
            12 , 64 , 35 , 29 , 59 , 9 , 83 , 73 , 21 , 61
        } ;
        int size = a.length ;
        for( int i = 0 ; i < size - 1 ; i++ ) {
            int tmp ;
            int m = i ;
            for( int j = i + 1 ; j < size ; j++ ) {
                if ( a[j] > a[m] )
                    m = j ;
            }
            tmp = a[i] ;
            a[i] = a[m] ;
            a[m] = tmp ;
        }
    }
}

このプログラムの処理時間T(N)は…

… i=0の時
… i=1の時
:
         … i=N-1の時

        …(参考 数列の和の公式)

となる。

オーダー記法

ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。

単純サーチ
２分探索法
最大選択法

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ		オーダーNのアルゴリズム
2分探索法		オーダー log N のアルゴリズム
最大選択法		オーダー N2 のアルゴリズム

練習問題

1. ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか？
2. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
   データ10000件なら何[sec]かかるか？
   (ヒント: 底変換の公式)
3. の処理時間を要するアルゴリズム(データ件数が変わっても処理時間は一定)を、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
4. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
   (ヒント: ロピタルの定理)

• 2と4の解説
• 1は、N→∞において、N² ≪ 2^Nなので、O(2^N) 。厳密に回答するなら、練習問題4と同様の証明が必要。
• 3は、O(1)。
  • 誤答の例：O(0)と書いちゃうと、T(N)=T_α×0=0になってしまう。
  • 事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)