Chapter 1 Basic Concepts 2009. 3. 16

알고리즘(Algorithm) 특정한 일을 수행하기 위한 명령어들의 유한 집합 알고리즘의 요건(criteria) 1. 입력 : (외부) 원인  0 2. 출력 : 결과  1 3. 명확성(definiteness) : 모호하지 않은 명확한 명령 4. 유한성(finiteness) : 반드시 종료 5. 유효성(effectiveness) : 각 명령은 기본적이고 실행 가능해야 함 알고리즘 기술 방법 자연어 기술 흐름도(flowchart) Pseudo-code Programming Language (예: C 언어)

알고리즘의 기술 (예 1.1) [선택 정렬] : n  1 개의 서로 다른 정수의 집합을 정렬하는 프로그램을 작성 방법: 정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓음 예: 3, 8, 1, 4, 7  1, 8, 3, 4, 7  1, 3, 8, 4, 7  1, 3, 4, 8, 7  1, 3, 4, 7, 8 for (i = 0; i < n; i++) [ list[i]에서부터 list[n-1]까지의 정수 값을 검사한 결과 list[j]가 가장 작은 값이라 하자; list[i]와 list[j]를 서로 교환함; }

선택 정렬 프로그램 void SelectionSort(int *list, const int n) // n개의 정수 list[0]부터 list[n-1]까지 비감소 순으로 정렬함. { for (int i = 0; i < n; i++) { int temp, min; // list[min]과 list[n-1] 사이의 가장 작은 정수 찾음 min = i; for (int k = i + 1; k < n; k++) if (list[k] < list[min]) min = k; temp = list[i]; list[i] = list[min]; list[min] = temp; // 교환 } 0 1 2 3 4 3, 8, 1, 4, 7  1, 8, 3, 4, 7  1, 3, 8, 4, 7  1, 3, 4, 8, 7  1, 3, 4, 7, 8

알고리즘의 기술 (예 1.2) [이진 탐색] : x = list[j]인 j를 찾음 가정: list의 원소들은 이미 정렬된 상태 left, right: 탐색하고자 하는 원소들의 왼쪽 및 오른쪽 끝 지점 초기 값: left = 0, right = n-1 middle: 탐색할 원소들의 중간 위치, 즉, middle = (left + right) / 2 list[middle]과 x를 비교할 경우 3가지 경우 중에 하나 ⑴ x > list[middle] 일 때: left를 middle+1로 설정 ⑵ x < list[middle] 일 때: right를 middle-1로 설정 ⑶ x = list[middle] 일 때: middle을 반환 left middle right 0 1 2 3 4 5 6 7 8 9 10 3 5 7 10 15 16 19 20 26 28 31 index list x = 26

이진 탐색 알고리즘 int BinarySearch(int *list, const int x, const int n) // 정렬된 배열 list[0], ..., list[n-1]에서 x를 탐색한다. { for (left와 right를 초기화한다; 원소가 더 있는 한 계속; ) // 가운데 원소를 middle로 설정한다. switch (compare(x, list[middle])) { case '>' : left를 middle + 1로 설정; break; case '<' : right = middle - 1로 설정; break; case '=' : x를 발견; } not found; char compare(int x, int y) { if (x > y) return '>'; else if (x < y) return '<'; else return '='; }

이진 탐색 함수 구현 int BinarySearch(int *list, const int x, const int n) // 정렬된 배열 list[0], ..., list[n-1]에서 x를 탐색한다. { for (int left = 0, right = n-1; left <= right; ) { int middle = (left + right) / 2; switch (comare(x, list[middle])) { case '>' : left = middle + 1; break; // x > list[middle] case '<' : right = middle - 1; break; // x < list[middle] case '=' : return middle; // x == list[middle] } return -1; // x가 list에 존재하지 않음

순환 알고리즘(Recursive Algorithms) 수행이 완료되기 전에 자기 자신을 다시 호출 직접 순환 : direct recursion 간접 순환 : indirect recursion 예 Factorial(!) : N! = N*(N-1)! 이항 계수(Binomial Coefficient) Fibonacci 수열 int FACT(int N) { if (N==0) return (1); else return (N*FACT(N-1)); } N*(N-1)*(N-2)*....*2*1*1

순환 알고리즘(Recursive Algorithms) 특징 장점: 실행 과정의 효율적 기술 복잡한 계산 과정을 단순하고 명료하게 표현 가능 문제 자체가 순환적으로 정의되는 경우에 적합 단점: 실행 효율 저하 실행 시간에 순환을 위한 별도의 준비 설정이 필요 공간 및 시간 복잡도 증가 일반적으로 배정문(assignment), 조건문(if-else), 반복문(while)으로 표현되는 반복 알고리즘은 순환 알고리즘으로 변환 가능

예1.3: 이진 탐색의 순환적 구현 int BinarySearch(int *list, const int x, const int left, const int right) // 정렬된 배열 list[left], ..., list[right]에서 x를 탐색 { if (left <= right) { int middle = (left + right) / 2; switch(compare(x, list[middle])) { case '>' : return BinarySearch(list, x, middle+1, right); case '<' : return BinarySearch(list, x, left, middle-1); case '=' : return middle; } return -1; // x가 발견되지 않음

예1.4: 순열 생성기 n1개의 원소로 된 집합으로부터 모든 가능한 순열을 출력 perm(a, b, c, d); 1) a + perm(b, c, d) 2) b + perm(a, c, d) 3) c + perm(b, a, d) 4) d + perm(b, c, a) perm(b, c, d) 1) b + perm(c, d) 2) c + perm(b, d) 3) d + perm(c, b) perm(c, d) 1) c + perm(d) 2) d + perm(c)

예1.4: 순열 생성기 void perm(char *list, const int k, const int n) { // n은 list의 크기 // list[k], ..., list[n-1]에 대한 모든 순열을 생성 if (k == n-1) { // 순열을 출력 for (int i = 0; i < n; i++) printf(“%c”, list[i]); printf(“\n”); } else{ // list[k], ..., list[n-1]에 있는 여러 순열을 순환적으로 생성 for (i = k; i < n; i++) { // list[k]와 list[i]를 교환 char temp = list[k]; list[k] = list[i]; list[i] = temp; perm(list, k+1, n); // list[k+1], ..., list[n-1]에 대한 모든 순열 // 원래 상태로 되돌리기 위해 list[k]와 list[i]를 다시 교환 temp = list[k]; list[k] = list[i]; list[i] = temp; } } perm(list, 0, n) 호출  list[0], list[1], …, list[n-1]에 대한 모든 순열 생성

데이터 타입(Data Type) 정의 C/C++의 데이터 타입 객체(object)와 그 객체 위에 작동하는 연산(operation)들의 집합 사전 정의(pre-defined) 데이터 타입 사용자 정의(user-defined) 데이터 타입 C/C++의 데이터 타입 기본 데이터 타입 char, int, float, double 타입 수식어: short, long, signed, unsigned 파생 데이터 타입 포인터(pointer) 타입, 참조(reference) 타입(C++) 데이터 집단화 구조 배열(array), 구조체(struct), 클래스(class)(C++)

데이터 캡슐화 및 추상화 데이터 캡슐화(Encapsulation) 데이터 추상화 외부에 대해 데이터 객체의 자세한 구현을 은폐시킴 객체의 내부 표현을 사용자로부터 은폐 (information hiding) 데이터 추상화 데이터 객체의 명세(specification)와 구현(implementation) 을 분리 “무엇(what)”과 “어떻게(how)”를 독립화 추상 데이터 타입(Abstract Data Type: ADT) 객체와 연산에 대한 명세를 객체의 표현 및 연산의 구현으로부터 분리시킨 데이터 타입 예: Ada언어의 Package, C++/Java언어의 Class ADT 연산의 명세 함수 이름, 매개 변수 타입, 결과 타입, 함수가 수행하는 기능에 대한 기술 내부적 표현이나 구현에 대한 자세한 설명은 제외됨

예: 자연수(Natural Number) 추상 데이터 타입 정의 예 ADT NaturalNumber is 객체: 순서가 있는 정수의 일부분으로 0부터 해당 컴퓨터의 최대 정수(MAXINT)까지의 값 함수: x, y  NaturalNumber, TRUE, FALSE  Boolean +, -, <, ==, = 는 일반 정수 연산자 Zero():NaturalNumber ::= 0 IsZero(x):Boolean ::= if (x == 0) IsZero = TRUE else IsZero = FALSE Add(x,y):NaturalNumber ::= if (x+y <= MAXINT) Add = x+y else Add = MAXINT Subtract(x,y):NaturalNumber ::= if (x<y) Subtract = 0 else Subtract = x-y Equal(x,y):Boolean ::= if (x == y) Equal = TRUE else Equal = FALSE Successor(x):NaturalNumber ::= if (x == MAXINT) Successor = x else Successor = x+1 end NaturalNumber

Stack ADT의 예 (C++) #include <iostream.h> class stack { // stack class 정의 private: int* stackPtr; int maxLen, topPtr; public: stack() { // constructor stackPtr = new int [100]; maxLen = 99; topPtr = -1; } ~stack() { delete[] stackPtr; } //destructor void push(int number); void pop(); int top() { return stackPtr[topPtr]; } int empty() { return (topPtr == -1); }

Stack ADT의 예 (C++) stack 클래스 이용 예 표준 C++ 라이브러리(standard C++ library) ISO 및 ANSI 표준 (ISO/IEC 14882) STL(Standard Template Library) 표준 데이터 구조에 대한 클래스 정의와 이러한 데이터 구조에 대한 주요 알고리즘 정의 http://oopsla.snu.ac.kr/~sjjung/stl/ 참조 void main() { int topOne; stack stk; // stack 클래스의 instance 생성 stk.push(42); stk.push(17); topOne = stk.top(); stk.pop(); … }

데이터 추상화 및 캡슐화의 장점 소프트웨어 개발의 간소화 검사와 디버깅의 단순화 재사용성 향상 데이터 타입 표현의 수정 용이 복잡한 작업을 여러 부분 작업들로 분해 검사와 디버깅의 단순화 부분 작업 재사용성 향상 자료 구조가 소프트웨어 시스템에서 독립적인 객체들로 구현되어 재사용 가능 데이터 타입 표현의 수정 용이 데이터 타입의 내부 구현을 직접 접근하는 부분만 변경 필요 그 이외 부분에는 무관 프로그램의 신뢰성 증가 객체는 ADT에서 제공되는 연산을 통해서만 변경 가능하므로 객체의 무결성 보장

성능 분석 및 측정 프로그램에 대한 평가 성능 평가 평가 기준 사전 예측  성능 분석(performance analysis) 명세에 부합 여부 정확히 작동 여부 문서화 논리적 작업 단위를 위한 함수의 효과적 이용 성능 평가 사전 예측  성능 분석(performance analysis)  시간과 공간의 추산 복잡도 이론(complexity theory) 이용 사후 검사  성능 측정(performance measurement)  컴퓨터 의존적인 실행 시간 측정 코드의 판독 용이성 메모리의 효율적 사용 적절한 실행 시간

성능 분석: 공간 복잡도 공간 복잡도(space complexity) S(P) = c + SP(I) 프로그램을 완전히 실행하는데 필요한 공간(메모리)의 양 고정 부분 프로그램 입출력 횟수나 크기와 관계없이 고정됨 예: 프로그램 코드, 단순 변수, 고정크기의 구조화 변수, 상수 등 가변 부분 입/출력의 수, 크기, 값 등 문제의 인스턴스(instance)의 특성에 의존 예: 가변 집단 변수, 순환 호출을 위한 스택 공간 등 프로그램 P의 공간 요구량 S(P) = c + SP(I) c : 상수(고정 부분에 해당) SP(I) : P의 인스턴스 I 에 의한 가변 공간 요구량

공간 복잡도 계산 예 예1.6: 단순 산술 함수 예1.7: 수치값 리스트 합산 함수 (반복적 구현) float abc(float a, float b, float c) {     return a+b+b*c + (a+b-c) / (a+b) + 4.00; } 고정 공간 요구만을 가짐 => Sabc(I) = 0 예1.7: 수치값 리스트 합산 함수 (반복적 구현) float sum(float list[], int n) {    float tempsum = 0;    int i;    for (i = 0; i < n; i++)       tempsum += list[i];    return tempsum; } 가변 공간 요구 : 배열 (크기 n) - 함수에 대한 배열의 전달 방식에 따라 다름  - 배열 전체의 복사 전달 (예: Pascal)         . Ssum(I) = Ssum(n) = n  - 배열의 첫번째 요소의 주소 전달 (예: C)         . Ssum(n) = 0

공간 복잡도 계산 예 예1.8: 수치값 리스트 합산 함수 (순환적 구현) float rsum(float list[], int n) {     if (n) return rsum(list, n-1) + list[n-1];     return 0; } - 함수 호출시 마다 매개 변수, 지역 변수, 복귀 주소를 저장해야 함 - 한번의 순환 호출을 위해 요구되는 공간   두 개의 매개 변수와 복귀 주소를 저장하기 위한 바이트 수                              ↱ list[]의 주소                       =  2    +    4    +    4  = 10                 ↳ sizeof(n)      ↳ 복귀주소 n = MAX_SIZE 일 때,           Srsum(MAX_SIZE) = 10 * MAX_SIZE

성능 분석: 시간 복잡도 시간 복잡도(time complexity) T(P) = c + TP(I) 프로그램을 완전히 실행시키는데 필요한 컴퓨터 시간의 양 프로그램에 의한 소요 시간 예: 산술 연산 프로그램 n: 인스턴스 특성 Ca, Cs, Cm, Cd : +, -, x, / 연산을 위한 상수 시간 ADD, SUB, MUL, DIV : 인스턴스 특성 n에 대한 연산 실행 횟수 T(P) = c + TP(I) c: 컴파일 시간  고정값 TP(I): 실행시간  인스턴스 특성 I에 따라 다름 TP(n) = Ca*ADD(n) + Cs*SUB(n) + Cm*MUL(n) + Cd*DIV(n)

성능 분석: 시간 복잡도 프로그램이 수행하는 연산의 횟수로 시간 복잡도를 추정 프로그램 단계(step) 프로그램 단계 수 (step count) 프로그램 단계(step) 실행 시간이 인스턴스 특성에 구문적으로나 의미적으로 독립성을 갖는 프로그램의 단위(세그먼트) 각 단계의 실행에 필요한 시간이 인스턴스 특성에 독립적이어야 함 예: 입력의 수 n에 대한 시간 복잡도 계산 시, n개의 정수들의 덧셈은 한 단계가 될 수 없음 각 단계의 실제 계산량은 서로 상이할 수 있음 예: a = 2; a = 2*b+c;

예1.9: 수치값 리스트 합산 함수 (반복) 2n+3 1. Counter 이용 float sum(float *list, const int n) { float s = 0; count++; // 배정문 for (int i = 0; i < n; i++) { count++; // for문 s += list[i]; count++; // 배정문 } count++; // for문의 마지막 실행 return s; count++; // return문 float sum(float *list, const int n) for (int i = 0; i < n; i++) count += 2; count += 3; 2n+3

예1.9: 수치값 리스트 합산 함수 (반복) 2. 단계수 Table 작성 행번호 s/e 빈도수 총 단계수 1 0 1 0 2 1 1 1 3 1 n+1 n+1 4 1 n n 5 1 1 1 6 0 1 0 tsum(n) = 2n+3 float sum(float *list, const int n) 1 { 2 float s = 0; 3 for(int i = 0; i < n; i++) 4 s += list[i]; 5 return s; 6 }

예1.10: 수치값 리스트 합산 함수 (순환) 단계 수 계산 float rsum(float *list, const int n) 1 { 2 if (n <= 0) return 0; 3 else return (rsum(list, n-1)+list[n-1]); 4 } 단계 수 계산 trsum(n) = 2 + trsum(n-1) = 2 + 2 + trsum(n-2) = 2 * 2 + trsum(n-2) … = 2n + trsum(0) = 2n + 2

시간 복잡도 계산 예 행렬의 덧셈 문 장 s/e 빈도수 총단계수 void add(int a[][MAX_SIZE] ··· ) { 문 장 s/e 빈도수 총단계수 void add(int a[][MAX_SIZE] ··· ) { int i, j; for (i=0, i<rows; i++) for(j=0, j<cols; j++) c[i][j] = a[i][j] + b[i][j] } 0 0 0 1 rows+1 rows+1 1 rows(cols+1) rows·cols+row 1 rows·cols rows·cols 합 계 2rows·cols+2rows+1

성능 분석: 시간 복잡도 프로그램 단계 수 프로그램 인스턴스 특성에 대한 함수 여러가지 특성들 중 관심이 있는 특성들에 대한 함수로 표현 예: 입력의 수의 증가에 대한 시간 복잡도, 특정 입력의 크기가 증가함에 따른 시간 복잡도 등 주어진 인스턴스 특성에 대해 단계 수를 유일하게 결정할 수 없는 경우 예: binary search 원소의 수 n 외에, 탐색 키의 위치에 따라 단계수가 달라짐 최악의 경우(worse-case), 최선의 경우(best-case), 평균(average-case) 단계 수 계산

점근 표기법(O, , ) Motivation 프로그램의 정확한 단계 수 계산 : 어렵고 무의미함 근사치 사용 동일 기능의 두 프로그램의 시간 복잡도 비교 인스턴스 특성의 변화에 따른 실행 시간 증가 예측 프로그램의 정확한 단계 수 계산 : 어렵고 무의미함 예: A의 단계수 = 3n + 3, B의 단계수 = 100n + 10 A ≃ 3n (or 2n), B ≃ 100n (or 80n, 85n) 근사치 사용  C1과 C2가 음이 아닌 상수일 때, C1n2 ≤ Tp(n) ≤ C2n2 또는 TQ(n,m) = C1n + C2m 등으로 표현 가능 충분히 큰 n에 대해 C1n2 + C2n > C3n 성립 예) C1= 1, C2 = 2, C3 = 100이고, n ≤ 98일때, C1n2 + C2n ≤ C3n, n  > 98일때, C1n2 + C2n  > C3n 즉, 손익분기점(break even point)은 n = 98 C1, C2, C3 및 손익분기점을 정확히 알아낼 필요는 없음

점근 표기법(O, , ) 정의: [Big "oh"] f(n) = Ο(g(n))  ∃c,n0 > 0, s.t. f(n) ≤ cg(n) for ∀n, n≥n0 예 n ≥ 2,  3n + 2 ≤ 4n ⇨  3n + 2 = Ο(n) n ≥ 3, 3n + 3 ≤ 4n ⇨  3n + 3 = Ο(n) n ≥ 10, 100n + 6 ≤ 101n  ⇨ 100n + 6 = Ο(n) n ≥ 5, 10n2 + 4n + 2 ≤ 11n2 ⇨ 10n2 + 4n + 2 = Ο(n2) n ≥ 4, 6*2n + n2 ≤ 7*2n ⇨  6*2n + n2 = Ο(2n) n ≥ 2, 3n + 3 ≤ 3n2 ⇨  3n + 3 = Ο(n2) n ≥ 2, 10n2 + 4n + 2 ≤ 10n4  ⇨  10n2 + 4n + 2 = Ο(n4) n ≥ n0인 모든 n과 임의의 상수 c에 대해, 3n + 2 ≤ c 가 false인 경우가 존재하므로 ⇨  3n+2≠Ο(1) 10n2 + 4n + 2 ≠ Ο(n)

점근 표기법(O, , ) order of magnitude O(1) : 상수(constant) O(log logn) : log log O(logn) : logarithmic O(n) : 선형(linear) O(nlogn) : log linear O(n2) : 평방형(quadratic) O(n3) : 입방형(cubic) O(2n) : 지수형(exponential) O(n!) : factorial

점근 표기법(O, , ) f(n) = Ο(g(n)) n ≥ n0인 모든 n에 대해 g(n) 값은 f(n)의 상한 값이라는 것을 의미 예: 3n+3 = O(n), 3n+3 = O(n2), 3n+3 = O(2n) 일반적으로 g(n)은 조건을 만족하는 가장 작은 함수여야 함 예: 3n+3 = O(n)으로 표현 정리: f(n) = amnm + … + a1n1+ a0  f(n) = O(nm) f(n) = O(g(n))  for some c R*

점근 표기법(O, , ) 정의: [Big "Omega"] f(n) = Ω(g(n))  ∃c,n0 > 0, s.t. f(n) ≥ cg(n) for ∀n, n≥n0 예 n ≥ 1, 3n + 2 ≥ 3n ⇨ 3n + 2 = Ω(n) n ≥ 1, 3n + 3 ≥ 3n ⇨ 3n + 3 = Ω(n) n ≥ 1, 100n + 6 ≥ 100n ⇨ 100n + 6 = Ω(n) n ≥ 1, 10n2 + 4n + 2 ≥ n2 ⇨ 100n2 + 4n + 2 = Ω(n2) n ≥ 1, 6*2n + n2 ≥ 2n ⇨ 6*2n + n2 = Ω(2n)

점근 표기법(O, , ) f(n) = Ω(g(n)) n ≥ n0인 모든 n에 대해 g(n) 값은 f(n)의 하한값이라는 것을 의미 예: 3n2+3 = Ω(n2), 3n2+3 = Ω(n), 3n2+3 = Ω(1) 일반적으로 g(n)은 조건을 만족하는 가장 큰 함수여야 함 예: 3n2+3 = Ω(n2)으로 표현 f(n) = Ω(g(n))  or

점근 표기법(O, , ) 정의: [Theta] f(n)=Θ(g(n))  ∃C1,C2,n0 > 0, s.t. C1g(n)≤f(n)≤C2g(n) for ∀n, n≥n0 예 n ≥ 2, 3n ≤ 3n + 2 ≤4n ⇨ 3n + 2 = Θ(n)  c1 = 3, c2 = 4, n0 = 2 3n + 3 = Θ(n) 10n2 + 4n + 2 = Θ(n2) 6*2n + n2 = Θ(2n)       10*log n + 4 = Θ(log n)

점근 표기법(O, , ) f(n)=Θ(g(n)) g(n)이 f(n)에 대해 상한 값과 하한 값을 모두 가지는 경우 f(n) = Θ(g(n))  for some c R+

점근 표기법(O, , ) 점근적 복잡도(asymptotic complexity: Ο,Ω,Θ) 정확한 단계수의 계산없이 쉽게 구할 수 있음 예: sum(float *a, const int n) float sum(float *a, const int n) 1 { 2 float s = 0; 3 for(int i = 0; i < n; i++) 4 s += list[i]; 5 return s; 6 } 행번호 s/e 빈도수 총 단계 1 0 0 Θ(0) 2 1 1 Θ(1) 3 1 n+1 Θ(n) 4 1 n Θ(n) 5 1 1 Θ(1) 6 0 1 Θ(0) tsum(n) = Θ(max{gi(n)}) = Θ(n)

점근 표기법(O, , ) 예제 [이진 탐색] 예제 [순열] 예제 [Magic Square] Worst-cast: Θ(log n) Best-case: Θ(1) 예제 [순열] Θ(n(n!)) 예제 [Magic Square] Θ(n2)

매직 스퀘어 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11 매직 스퀘어의 예

void magic(int n) // 크기가 n이고 n은 홀수인 매직 스퀘어를 생성 { const int MaxSize = 51; // 스퀘어의 최대 크기 int square[Max_Size][Max_Size], k, l; // n이 올바른 값인지 검사 if((n > (Max_Size)) || (n < 1)){ cerr << "Error! ... n out of range" <<endl; return; } else if(!(n%2)) { cerr << "Error! ... n is even" << endl; return; // n이 홀수. Coxeter의 규칙이 사용됨 for(int i = 0; i < n; i++) // square를 0으로 초기화 for(int j = 0; j < n; j++) square[i][j] = 0; square[0][(n-1)/2] = 1; // 첫 행의 중간 // i와 j는 현재 위치 int key = 2; i = 0; int j = (n-1)/2;

while(key <= n * n){ // 왼쪽 위로 이동 if(i - 1 < 0) k = n - 1; else k = i - 1; if(j - 1 < 0) l = n - 1; else l = j - 1; if(square[k][l]) i = (i + 1) % n; // square가 채워짐. 아래로 이동 else{ // square[k][l]이 채워지지 않음 i = k; j = l; } square[i][j] = key; key++; // 매직 스퀘어를 출력 cout << "magic square of size" << n << endl; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) cout << square[i][j] << " "; cout << endl;

실용적 복잡도 매우 큰 n에 대해서는, 작은 시간 복잡도를 가진 프로그램(알고리즘)만이 실제적으로 사용 가능함

실용적 복잡도 If a program needs 2n steps for execution, n=40 --- number of steps = 1.1*1012 in computer systems performing 1 billion steps/sec --- 18.3 min n=50 --- 13 days n=60 --- 310.56 years n=100 --- 4*1013 years