/algorithms

Collection of resuable algorithm templates written in pure C++

Primary LanguageC++

Algorithms

Algorithms stuff created on my own, grabbed from some resources and all of them are putted here.

Methodology

This repository of ready-to-use algorithms follows a methodology that makes algorithms easy to find, extend and copy to your existing code. Every algorithm that is here needs to be:

  • In separated file need to work sreperatly, without using any sources or algorithms from another one.
  • Easy to copy and paste into your own code.
  • Is supposed to be fast, not necessarily readable

Note
Usefull for creating memory-efficent algorithms are sizes of each types in C++, they are listed in sizes file

Tasks

List of currently implemented algorithms:

  • Prefix sums Answers: O(1)

    • 2d sums O(n * m)
    • Normal sums O(n)
    • Sums on overlapping intervals O(n)

  • Math

    • Is a prime number O(sqrt2(n))
    • Euklides NWD O(log2(max(n, k)))
    • Euklides NWW O(log2(max(n, k)))
    • Advenced euklides O(log2(max(n, k)))
    • The sieve of Eratosthenes O(n log2(log2(n)))
    • Number of dividers
    • Remembered factorial
    • Permutations

  • Trees O(log2(n))

    • Range-Range Tree
    • Point-to-Range Tree
    • Range-to-Point Tree

  • Graphs

    • Dijkstra algorithm O(m log2(n))
    • BFS for:
      • Graph O(n+m)
      • Grid O(n*m)
    • DFS for:
      • Graph: O(n+m)
      • Grid O(n*m)

  • Sparses

    • Range Minimum Queries O(n log n) O(1)
    • Range Sum Queries (is simmilar to prefix sums but much slower)

  • Other

    • Caterpillar algorithm O(2 * n)
    • Merge sort O(n log n)
    • Binary Search O(log2(n))
    • Bubble sort O(n^2)

Credits

Thanks for help from various internet sources including software engineering forums and CpAlgorithms