Skip to content

PrinceNet/PHP-Algorithms

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

29 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

PHP Algorithms

Here I will add a handful of algorithms from many fields I find useful and interesting.

Euclidean (aka GCD)

Preview
GCD stands for Greatest Common Divisor.
Given 2 natural numbers, find their greatest common divisor that divides both of them without leaving any reminder.

Time Complexity: O(log min(a, b))

Euclidean Extended (aka GCD Extended)

Preview
Same as the Euclidean algorithm but this algorithm also brings us 2 numbers x, y that satisfy the following equation:
gcd(a, b) = ax + by = d

Time Complexity: O(log min(a, b))

Least Common Multiple (aka LCM)

Preview
Given 2 natural numbers a, b, find the smallest positive integer that is divisible by both a and b.

Time Complexity: O(log min(a, b))

Kadane (aka Maximum Subarray Problem)

Preview
Finding the contiguous subarray within a one-dimensional array.

Time Complexity: O(n)

Binary Search

Preview
Finds the position (index) of a target value within a sorted array.

Time Complexity: O(log n)

Insertion Sort

Preview
Simple sorting algorithm.

Time Complexity: O(n^2)

String Sum

Preview
Given 2 big natural numbers, sum them together.

Time Complexity: O(max(|str1|, |str2|))

Fisher Yates Shuffle

Preview
Given an array, shuffle the elements randomly.

Time Complexity: O(n)

Is Prime (Simple Version)

Preview
Given a integer number, check if the number is prime or not.

Time Complexity: O(sqrt(n))

Sieve of Eratosthenes

Preview
Compute all the prime numbers that are smaller than or equal to n.

Time Complexity: O(n * log(log(n)))

Prime Factorization

Preview
Compute all the prime factors of n.

Time Complexity: O(sqrt(n))

Euler's Totient Function

Preview
Counts the positive integers up to a given integer n that are relatively prime to n.

Time Complexity: O(sqrt(n))

KMP (Knuth–Morris–Pratt string-searching)

Preview
Given a word of size m and a text of size n, searches for all occurrences of a word within a text.

Time Complexity: O(n + m)

Modular Exponentiation

Preview
Efficient way to compute (x ^ n) % m.

Time Complexity: O(log n)

Modular Multiplicative Inverse

Preview
Given a and m, finds x such that: (a * x) mod m = 1

Time Complexity: O(log min(a, m))

Binomial Coefficient

Preview
nCk = n! / k! * (n - k)!
where n >= k >= 0

Time Complexity: O(k)

Activity Selection

Preview
Given n activities with their start and finish times.
Select the maximum number of activities that can be performed by a single person or machine,
assuming that a person can only work on a single activity at a time

Time Complexity: O(n * log n)

Graph (Data Structure)

Preview
Will be used in graph algorithms later on.
Assuming each node is connected to at least one other node.
Can be direcred/undirecred and/or weighted/unweighted.
Using adjacency list.

DFS (Depth First Search)

Preview
Traversing/searching a graph data structure.
Explores as far as possible along each branch before backtracking.
V is the number of vertices. E is the number edges.

Time Complexity: O(V + E)

Floyd Warshall

Preview
Finding all shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).

Time Complexity: O(V^3)

Point (Data Structure)

Preview
Will be used in geometry algorithms later on.
2D point.

Polygon Area

Preview
Find any polygon area.
n is the amount of points of the polygon.

Time Complexity: O(n)

Polygon Perimeter

Preview
Find any polygon perimeter.
n is the amount of points of the polygon.

Time Complexity: O(n)

License

All algorithms are licensed under the MIT license.

Have fun!

About

Algorithms written in PHP

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages