Kompleksitas Algoritma – ryandhikafm's blog

Disini saya akan memberi contoh algoritma untuk masing-masing kompleksitas

O(1): Kompleksitas Konstan

void add_list(node *anchor, node *new_list)

{

new_list->next = anchor->next;

anchor->next = new_list;

}

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

int main()

{

int x, y;

printf(“Enter Value of x “);

scanf(“%d”, &x);

printf(“\nEnter Value of y “);

scanf(“%d”, &y);

swap(&x, &y);

printf(“\nAfter Swapping: x = %d, y = %d”, x, y);

return 0;

}

procedure push(stk : stack, x : item):

if stk.top = stk.maxsize:

report overflow error

else:

stk.items[stk.top] ← x

stk.top ← stk.top + 1

procedure pop(stk : stack):

if stk.top = 0:

report underflow error

else:

stk.top ← stk.top − 1

r ← stk.items[stk.top]

procedure addq (item : items);
{add item to the queue q}
begin
if rear=n then queuefull
else begin
rear :=rear+1;
q[rear]:=item;
end;
end;{of addq}

O(log n): Kompleksitas Logaritmik

def binary_search(lst, search):

lower_bound = 0

upper_bound = len(lst) – 1

while True:

if upper_bound < lower_bound:

print(“Not found.”)

return -1

i = (lower_bound + upper_bound) // 2

if lst[i] < search:

lower_bound = i + 1

elif lst[i] > search:

upper_bound = i – 1

else:

print(“Element ” + str(search) + ” in ” + str(i))

return 0

int binarySearch(int arr[], int l, int r, int x)

{

while (l <= r)

{

int m = l + (r-l)/2;

if (arr[m] == x) return m; // Check if x is present at mid

if (arr[m] < x) l = m + 1; // If x greater, ignore left half

else r = m – 1; // If x is smaller, ignore right half

}

return -1; // if we reach here, then element was not present

}

int main(void)

{

int arr[] = {2, 3, 4, 10, 40};

int n = sizeof(arr)/ sizeof(arr[0]);

int x = 10;

int result = binarySearch(arr, 0, n-1, x);

(result == -1)? printf(“Element is not present in array”)

: printf(“Element is present at index %d”, result);

return 0;

}

var right = function(str){

var length = str.length;

var help = function(index){

if(index < length){

console.log(str.substring(index, length));

help(Math.ceil((length + index)/2));

}

}

help(0);

}

void printNthNode(Node* root, int N)

{

if(root == NULL)

return;

static int index = 0;

printNthNode(root->right, N);

if(++index == N)

{

printf(“%d\n”, root->data);

return;

}

printNthNode(root->left, N);

}

#include <stdio.h>

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

int fib(int n)

{

int F[2][2] = {{1,1},{1,0}};

if (n == 0)

return 0;

power(F, n-1);

return F[0][0];

}

void power(int F[2][2], int n)

{

if( n == 0 || n == 1)

return;

int M[2][2] = {{1,1},{1,0}};

power(F, n/2);

multiply(F, F);

if (n%2 != 0)

multiply(F, M);

}

void multiply(int F[2][2], int M[2][2])

{

int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];

int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];

int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];

int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;

F[0][1] = y;

F[1][0] = z;

F[1][1] = w;

}

int main()

{

int n = 9;

printf(“%d”, fib(9));

getchar();

return 0;

}

O(n): Kompleksitas Linear

def linear_search(lst, search):

for i in range(0, len(lst)):

if lst[i] == search:

print(“Nilai ditemukan pada posisi ” + str(i))

return 0

print(“Nilai tidak ditemukan.”)

return -1

$numbers = array(14,82,4,0,24,28);

foreach($numbers as $number)

{

echo $number;

}

$numbers = array(14,82,4,0,24,28);

foreach($numbers as $number1)

{

foreach($numbers as $number2)

{

if($number1 >= $number2)

{

echo $number1 . ” is greater than or equal to ” . $number2;

}

else

{

echo $number1 . ” is smaller than ” . $number2;

}

}

}

foreach($numbers as $number)

{

echo $number;

}

public class SinglyLinkedList {

…

public int traverse() {

int sum = 0;

SinglyLinkedListNode current = head;

SinglyLinkedListNode previous = null;

while (current != null) {

sum += current.value;

previous = current;

current = current.next;

}

return sum;

}

}

Select(A,n,i):

Divide input into ⌈n/5⌉ groups of size 5.

/* Partition on median-of-medians */

medians = array of each group’s median.

pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)

Left Array L and Right Array G = partition(A, pivot)

/* Find ith element in L, pivot, or G */

k = |L| + 1

If i = k, return pivot

If i < k, return Select(L, k-1, i)

If i > k, return Select(G, n-k, i-k)

#include<stdio.h>

#include<conio.h>

void main()

{

clrscr();

int a[10];

int i,n;

printf(“enter no of elements:”);

scanf(“%d”,&n);

printf(“enter array:”);

for(i=1;i<=n;i++)

{

scanf(“%d”,a[i]);

}

printf(“entered array is”);

for(i=1;i<=n;i++)

{

printf(“%d”,a[i]);

}

getch();

}

O(n log n)

def zero_sum(lst):

n = len(lst)

for i in range(0, n):

j = binary_search(lst, -1 * lst[i])

if j > i:

n1 = str(lst[i])

n2 = str(lst[j])

print(“Zero sum: ” + n1 + ” and ” + n2 + “\n”)

function quicksort(array)

if length(array) > 1

pivot := select any element of array

left := first index of array

right := last index of array

while left ≤ right

while array[left] < pivot

left := left + 1

while array[right] > pivot

right := right – 1

if left ≤ right

swap array[left] with array[right]

left := left + 1

right := right – 1

quicksort(array from first index to right)

quicksort(array from left to last index)

procedure heapify(a,count) is

(end is assigned the index of the first (left) child of the root)

end := 1

while end < count

(sift up the node at index end to the proper place such that all nodes above

the end index are in heap order)

siftUp(a, 0, end)

end := end + 1

(after sifting up the last node all nodes are in heap order)

procedure siftUp(a, start, end) is

input: start represents the limit of how far up the heap to sift.

end is the node to sift up.

child := end

while child > start

parent := floor((child-1) / 2)

if a[parent] < a[child] then (out of max-heap order)

swap(a[parent], a[child])

child := parent (repeat to continue sifting up the parent now)

else

return

def mergeSort(alist):

print(“Splitting “,alist)

if len(alist)>1:

mid = len(alist)//2

lefthalf = alist[:mid]

righthalf = alist[mid:]

mergeSort(lefthalf)

mergeSort(righthalf)

i=0

j=0

k=0

while i < len(lefthalf) and j < len(righthalf):

if lefthalf[i] < righthalf[j]:

alist[k]=lefthalf[i]

i=i+1

else:

alist[k]=righthalf[j]

j=j+1

k=k+1

while i < len(lefthalf):

alist[k]=lefthalf[i]

i=i+1

k=k+1

while j < len(righthalf):

alist[k]=righthalf[j]

j=j+1

k=k+1

print(“Merging “,alist)

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

const double TwoPi = 6.283185307179586;

void FFTAnalysis(double *AVal, double *FTvl, int Nvl, int Nft) {

int i, j, n, m, Mmax, Istp;

double Tmpr, Tmpi, Wtmp, Theta;

double Wpr, Wpi, Wr, Wi;

double *Tmvl;

n = Nvl * 2; Tmvl = new double[n+1];

for (i = 0; i <Nvl; i++) {

j = i * 2; Tmvl[j] = 0; Tmvl[j+1] = AVal[i];

}

i = 1; j = 1;

while (i <n) {

if (j> i) {

Tmpr = Tmvl[i]; Tmvl[i] = Tmvl[j]; Tmvl[j] = Tmpr;

Tmpr = Tmvl[i+1]; Tmvl[i+1] = Tmvl[j+1]; Tmvl[j+1] = Tmpr;

}

i = i + 2; m = Nvl;

while ((m>= 2) && (j> m)) {

j = j – m; m = m>> 2;

}

j = j + m;

}

Mmax = 2;

while (n> Mmax) {

Theta = -TwoPi / Mmax; Wpi = Sin(Theta);

Wtmp = Sin(Theta / 2); Wpr = Wtmp * Wtmp * 2;

Istp = Mmax * 2; Wr = 1; Wi = 0; m = 1;

while (m <Mmax) {

i = m; m = m + 2; Tmpr = Wr; Tmpi = Wi;

Wr = Wr – Tmpr * Wpr – Tmpi * Wpi;

Wi = Wi + Tmpr * Wpi – Tmpi * Wpr;

while (i <n) {

j = i + Mmax;

Tmpr = Wr * Tmvl[j] – Wi * Tmvl[j+1];

Tmpi = Wi * Tmvl[j] + Wr * Tmvl[j+1];

Tmvl[j] = Tmvl[i] – Tmpr; Tmvl[j+1] = Tmvl[i+1] – Tmpi;

Tmvl[i] = Tmvl[i] + Tmpr; Tmvl[i+1] = Tmvl[i+1] + Tmpi;

i = i + Istp;

}

}

Mmax = Istp;

}

for (i = 1; i <Nft; i++) {

j = i * 2; FTvl[i] = Sqrt(Sqr(Tmvl[j]) + Sqr(Tmvl[j+1]));

}

delete []Tmvl;

}

O(n²): Kompleksitas Kuadratik

for(int j=0; j<N; j++){

for(int i=0; i<N; i++) {

a = max(a, i*j); }}

$numbers = array(14,82,4,0,24,28);

foreach($numbers as $number1)

{

foreach($numbers as $number2)

{

if($number1 >= $number2)

{

echo $number1 . ” is greater than or equal to ” . $number2;

}

else

{

echo $number1 . ” is smaller than ” . $number2;

}

}

}

function insertionSort($array)

{

$currentNumber;

for($i = 1; $i < count($array); $i++)

{

$currentNumber = $array[$i];

while (($i-1 >= 0) && ($currentNumber < $array[$i-1])) //While there is a smaller number to the left

{

$array[$i] = $array[$i-1]; //replace the current number by the number to its left

$i–;

}

//there are no smaller numbers to the left anymore

$array[$i] = $currentNumber; //set the current number to the number that originally had index i

}

return $array;

}

void insertionSort(int arr[], int n)

{

int i, key, j;

for (i = 1; i < n; i++)

{

key = arr[i];

j = i-1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > key)

{

arr[j+1] = arr[j];

j = j-1;

}

arr[j+1] = key;

}

}

// A utility function ot print an array of size n

void printArray(int arr[], int n)

{

int i;

for (i=0; i < n; i++)

printf(“%d “, arr[i]);

printf(“\n”);

}

/* Driver program to test insertion sort */

int main()

{

int arr[] = {12, 11, 13, 5, 6};

int n = sizeof(arr)/sizeof(arr[0]);

insertionSort(arr, n);

printArray(arr, n);

return 0;

}

int i,j;

int iMin;

for (j = 0; j < n-1; j++) {

iMin = j;

for ( i = j+1; i < n; i++) {

if (a[i] < a[iMin]) {

iMin = i;

}

}

if(iMin != j) {

swap(a[j], a[iMin]);

}

}

O(n³): Kompleksitas Kubik

include <iostream>

int main(int argc, const char * argv[])

{

int n = 9;

int index_I = 0;

int index_J = 0;

int index_K = 0;

for (int i = 1; i < n; i++) {

for (int j = i+1; j <= n; j++) {

for (int k = i; k <= j; k++) {

index_K++;

}

index_J++;

}

index_I++;

}

std::cout << index_I << std::endl;

std::cout << index_J << std::endl;

std::cout << index_K << std::endl;

return 0;

}

#

for (int i=0; i< n; i++) {

for (int j=0; j< n; j++) {

for (int k=0; k< n; k++) {

do_something(i, j, k);

}

}

}

def Matrix(a,b):

result = []

for i in range(0,len(a)):

new_array = []

result.extend(new_array)

for j in range(0,len(b[0])):

ssum = 0

for k in range(0,len(a[0])):

ssum += a[i][k] * b[k][j]

result[i][j] = ssum

return result

for k = 1 … min(m,n):

i_max := argmax (i = k … m, abs(A[i, k]))

if A[i_max, k] = 0

error “Matrix is singular!”

swap rows(k, i_max)

for i = k + 1 … m:

for j = k + 1 … n:

A[i, j] := A[i, j] – A[k, j] * (A[i, k] / A[k, k])

A[i, k] := 0

for i=1 to n

for j=1 to n

c[i][j]=0

for k=1 to n

c[i][j] = c[i][j]+a[i][k]*b[k][j]

O(2ⁿ): Kompleksitas Eksponensial

import random

def primesbelow(N):

# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188

#””” Input N>=6, Returns a list of primes, 2 <= p < N “””

correction = N % 6 > 1

N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]

sieve = [True] * (N // 3)

sieve[0] = False

for i in range(int(N ** .5) // 3 + 1):

if sieve[i]:

k = (3 * i + 1) | 1

sieve[k*k // 3::2*k] = [False] * ((N//6 – (k*k)//6 – 1)//k + 1)

sieve[(k*k + 4*k – 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 – (k*k + 4*k – 2*k*(i%2))//6 – 1) // k + 1)

return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 – correction) if sieve[i]]

smallprimeset = set(primesbelow(100000))

_smallprimeset = 100000

def isprime(n, precision=7):

# http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time

if n < 1:

raise ValueError(“Out of bounds, first argument must be > 0”)

elif n <= 3:

return n >= 2

elif n % 2 == 0:

return False

elif n < _smallprimeset:

return n in smallprimeset

d = n – 1

s = 0

while d % 2 == 0:

d //= 2

s += 1

for repeat in range(precision):

a = random.randrange(2, n – 2)

x = pow(a, d, n)

if x == 1 or x == n – 1: continue

for r in range(s – 1):

x = pow(x, 2, n)

if x == 1: return False

if x == n – 1: break

else: return False

return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/

def pollard_brent(n):

if n % 2 == 0: return 2

if n % 3 == 0: return 3

y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)

g, r, q = 1, 1, 1

while g == 1:

x = y

for i in range(r):

y = (pow(y, 2, n) + c) % n

k = 0

while k < r and g==1:

ys = y

for i in range(min(m, r-k)):

y = (pow(y, 2, n) + c) % n

q = q * abs(x-y) % n

g = gcd(q, n)

k += m

r *= 2

if g == n:

while True:

ys = (pow(ys, 2, n) + c) % n

g = gcd(abs(x – ys), n)

if g > 1:

break

return g

smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000

def primefactors(n, sort=False):

factors = []

for checker in smallprimes:

while n % checker == 0:

factors.append(checker)

n //= checker

if checker > n: break

if n < 2: return factors

while n > 1:

if isprime(n):

factors.append(n)

break

factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent

factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent

n //= factor

if sort: factors.sort()

return factors

def factorization(n):

factors = {}

for p1 in primefactors(n):

try:

factors[p1] += 1

except KeyError:

factors[p1] = 1

return factors

totients = {}

def totient(n):

if n == 0: return 1

try: return totients[n]

except KeyError: pass

tot = 1

for p, exp in factorization(n).items():

tot *= (p – 1) * p ** (exp – 1)

totients[n] = tot

return tot

def gcd(a, b):

if a == b: return a

while b > 0: a, b = b, a % b

return a

def lcm(a, b):

return abs((a // gcd(a, b)) * b)

public class TwoToTheN

{

private static int twoToTheN = 0;

private static int power = 3;

public static void main(String[] args)

{

twoToTheN(power);

System.out.println(twoToTheN);

}

private static void twoToTheN(int n)

{

if(n == 0)

{

twoToTheN++;

return;

}

else if(n == 1)

{

twoToTheN++;

twoToTheN++;

return;

}

twoToTheN(n-1);

twoToTheN(n-1);

}

}

Identify a hub vertex h

V_H = V – {h}

for each i,j != h

compute savings(i,j)

endfor

sortlist = Sort vertex pairs in decreasing order of savings

while |V_H| > 2

try vertex pair (i,j) in sortlist order

if (i,j) shortcut does not create a cycle

and degree(v) ≤ 2 for all v

add (i,j) segment to partial tour

if degree(i) = 2

V_H = V_H – {i}

endif

if degree(j) = 2

V_H = V_H – {j}

endif

endif

endwhile

Stitch together remaining two vertices and hub into final tour

public int fibonacci(int n) {

if(n == 0)

return 0;

else if(n == 1)

return 1;

else

return fibonacci(n – 1) + fibonacci(n – 2);

}

unsigned Fib(unsigned n)

{

if (n <= 1)

return n;

else

return Fib(n – 1) + Fib(n – 2);

}

O(n!): Kompleksitas Faktorial

def detPartSpecSubSize(n: Int, Nmin: Int, Nmax: Int): List[List[List[Int]]] = {

val all = (1 to n).toList

val cardinalityList = (Nmin to Nmax).toSet + 1

def _detPartSpecSubSize(elements: Set[Int]): Set[Set[List[Int]]] = {

def subsets(card: Int): List[List[Int]] = {

def _subsets(elements_ : Set[Int], n: Int): Set[Set[Int]] = {

if (n == 0 || elements_.size < n) Set(Set())

else {

for {

elem <- elements_

moreElem <- _subsets(elements_ – elem, n – 1)

if (1 + moreElem.size == n)

} yield (moreElem + elem)

}

}

_subsets(elements, card).toList.map(_.toList)

}

if (elements.size == 0) Set(Set())

else {

for {

c <- cardinalityList

part <- subsets(c)

if (part.length == c)

rest = elements — part.toSet

more <- _detPartSpecSubSize(rest.toSet)

} yield more + part

}

}

_detPartSpecSubSize(all.toSet).toList.map(_.toList)

}

function bozosort(array)

while !ordered(array)

swap(array[random1], array[random2])

def permutation(array, start, result)

if (start == array.length) then

result << array.dup

end

for i in start..array.length-1 do

array[start], array[i] = array[i], array[start]

permutation(array, start+1,result)

array[start], array[i] = array[i], array[start]

end

result

end

p permutation([1,2,3], 0, []).count #> 6 = 3!

p permutation([1,2,3,4], 0, []).count #> 24 = 4!

p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!

term_list = []

#If more than 2 rows, reduce and solve in a piecewise fashion

if X.cols>2:

for j in xrange(0,X.cols):

#Remove i and j columns

new_x = deepcopy(X)

del new_x[0]

new_x.del_column(j)

#Find the multiplier

multiplier = X[0][j] * math.pow(-1,(2+j))

#Recurse to find the determinant

det = recursive_determinant(new_x)

term_list.append(multiplier*det)

return sum(term_list)

else:

return(X[0][0]*X[1][1] – X[0][1]*X[1][0]) “`

import Data.List

import qualified Data.List.Key as K

dist :: Floating a => (a, a) -> (a, a) -> a

dist (x1, y1) (x2, y2) = sqrt ((x1 – x2) ** 2 + (y1 – y2) ** 2)

tours :: [b] -> [[(Int, b)]]

tours = map (\(x:xs) -> x:xs ++ [x]) . permutations . zip [0..]

cost :: Floating a => [(b, (a, a))] -> a

cost xs = sum $ zipWith dist xs (tail xs)

shortestPath :: [(Double, Double)] -> [Int]

shortestPath = init . map fst . K.minimum cost . tours