2차 행렬 곱셈

#include <iostream>
#include <chrono>

using namespace std;
using namespace chrono;


const int N = 200;

int main() {

    system_clock::time_point start = system_clock::now();

    int a[N][N];
    fill_n(a[0], N * N, 1);
    int b[N][N];
    fill_n(b[0], N * N, 2);
    int c[N][N];
    fill_n(c[0], N * N, 3);

    int arr[N][N] = { 0 };
    int result[N][N] = { 0 };


    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                arr[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                result[i][j] += arr[i][k] * c[k][j];
            }
        }
    }
    system_clock::time_point end = system_clock::now();

    microseconds microSec = duration_cast<microseconds>(end - start);

    cout << microSec.count() << "us" << endl;
}

3중 for문을 통해 2차 행렬 곱셈을 구현하였다.
2차 행렬에는 임의로 1,2,3 의 값을 넣어주었다.
시간 복잡도(Time Complexity) : N^3

다른 구현 방법

#include <iostream>
#include <ctime>


#define MAXLEN 800

using namespace std;

void matmul(int m1[][MAXLEN], int m2[][MAXLEN], int res[][MAXLEN], int size){
    for(size_t i = 0; i < size; i++){
        for(size_t j = 0; j < size; j++){
            res[i][j] = 0;
            for(size_t k = 0; k < size; k++){
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
}

int main(){
    int m1[MAXLEN][MAXLEN], m2 [MAXLEN][MAXLEN], res[MAXLEN][MAXLEN];
    int tic, toc;

    for(int n :  {200,400,600,800}){
        tic = clock();
        matmul(m1, m2, res, n);
        toc = clock();
        cout << n << ": " << toc - tic << endl;

    }
    return 0;
}

피보나치 수열

#include <iostream>
#include <chrono>

using namespace std;
using namespace chrono;

int Fibonacci(int num) {
	if (num == 1)
		return 1;

	if (num == 2)
		return 1;


	return Fibonacci(num - 1) + Fibonacci(num - 2);

}

int main() {
	system_clock::time_point start = system_clock::now();

	Fibonacci(30);

	system_clock::time_point end = system_clock::now();

	microseconds microSec = duration_cast<microseconds>(end - start);

	cout << microSec.count() << "us" << endl;
}

재귀함수로 구현하였다.
시간 복잡도(Time Complexity) : 2^n

다른 구현 방법

#include <iostream>
#include <ctime>

using namespace std;

int fib(int n){
    if(n <= 2)
        return 1;
    else
        return fib(n-1)+fib(n-2);
}

int main(){
    int tic, toc;
    for (int n : {30, 31, 32, 33 }){
        tic = clock();
        fib(n);
        toc = clock();
        cout << n << ": " << toc - tic << endl;
    }

    return 0;
}