Skip to content

williamkoller/introduction-analysis-algorithms-big-o

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

26 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Introdução à análise de Algoritmo e Big-O

book

1 - Por que eh importante saber Big-O?

Saber Big-O é importante porque permite determinar a complexidade de um algoritmo em relação ao tamanho da entrada. Isso ajuda a identificar algoritmos eficientes e escaláveis para lidar com grandes quantidades de dados e muitas requisições simultâneas. Empresas como Google, Amazon e Microsoft frequentemente fazem perguntas sobre complexidade de algoritmos durante o processo de seleção de candidatos

2 - Vamos falar sobre desempenho?

O desempenho de um algoritmo é fundamental para a eficiência e escalabilidade de uma solução. Compreender como medir e melhorar o desempenho é essencial para criar soluções eficientes e escaláveis. Além disso, muitas empresas valorizam o conhecimento desses conceitos durante o processo de seleção dos candidatos.

pensando-codigo

3 - Vamos falar sobre desempenho, do jeito certo?

Medir o desempenho de um algoritmo requer técnicas adequadas para obter resultados precisos. É importante evitar armadilhas comuns, como medir o tempo de execução em um ambiente não controlado ou medir apenas um caso específico em vez de uma amostra representativa de entradas.

4 - Vamos falar sobre complexidade linear?

A complexidade linear descreve um algoritmo cujo tempo de execução aumenta linearmente com o tamanho da entrada. Isso significa que o tempo de execução é proporcional ao número de elementos na entrada.

Exemplo codigo linear:

def sum_array_complexity(arr):
    total = 0
    for i in arr:
        total += i
    return total
def linear_search(array, target):
    for i in range(len(array)):
        if array[i] == target:
            return i
    return -1

complexidade-linear

5 - Vamos falar sobre complexidade constante?

A complexidade constante descreve um algoritmo cujo tempo de execução não varia com o tamanho da entrada. Isso significa que o tempo de execução é constante, independentemente do número de elementos na entrada.

Examplo codigo constante:

def sum_first_two(arr):
    if len(arr) >= 2:
        return arr[0] + arr[1]
    else:
        return None

complexidade-constante

6 - Vamos falar sobre complexidade logarítmica?

A complexidade logarítmica descreve um algoritmo cujo tempo de execução aumenta logaritmicamente com o tamanho da entrada. Isso significa que o tempo de execução é proporcional ao logaritmo do número de elementos na entrada.

Exemplo codigo logaritmico:

def logarithm(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low+high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
def euclidean_search(a, b):
    while b:
        a, b = b, a % b
    return a

complexidade-logaritmica

7 - Vamos falar sobre complexidade quadratica?

A complexidade quadrática descreve um algoritmo cujo tempo de execução aumenta quadraticamente com o tamanho da entrada. Isso significa que o tempo de execução é proporcional ao quadrado do número de elementos na entrada.

Exemplo codigo quadratica:

def sum_square_matrix(matrix):
    n = len(matrix)
    total = 0
    for i in range(n):
        for j in range(n):
            total += matrix[i][j]
    return total
def pair_sum(arr, target):
    pairs = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] + arr[j] == target:
                pairs.append((arr[i], arr[j]))
    return pairs

complexidade-quadratica

8 - Vamos falar sobre complexidade cubica?

A complexidade cúbica descreve um algoritmo cujo tempo de execução aumenta cúbicamente com o tamanho da entrada. Isso significa que o tempo de execução é proporcional ao cubo do número de elementos na entrada.

Exemplo codigo cubica:

def multiply_matrices(A, B):
    n = len(A)
    C = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

complexidade-cubica

9 - Vamos falar sobre complexidade exponencial?

A complexidade exponencial descreve um algoritmo cujo tempo de execução aumenta exponencialmente com o tamanho da entrada. Isso significa que o tempo de execução é proporcional a uma constante elevada à potência do número de elementos na entrada.

Exemplo codigo exponencial:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
def cubic_complexity_algorithm(n):
    result = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result += 1
    return result

complexidade-exponencial

10 - Vamos falar sobre complexidade fatorial?

A complexidade fatorial descreve um algoritmo cujo tempo de execução aumenta fatorialmente com o tamanho da entrada. Isso significa que o tempo de execução é proporcional ao fatorial do número de elementos na entrada.

def permutations(arr):
    if len(arr) == 0:
        return [[]]
    else:
        total = []
        for i in range(len(arr)):
            remaining_elements = arr[:i] + arr[i+1:]
            sub_permutations = permutations(remaining_elements)
            for permutation in sub_permutations:
                total.append([arr[i]] + permutation)
        return total

complexidade-fatorial

11 - Vamos comecar a falar sobre Big-O?

Big-O é uma notação matemática que descreve o comportamento de tempo de execução de um algoritmo em relação ao tamanho da entrada. Isso permite comparar algoritmos independentemente do hardware ou linguagem de programação usada para implementá-los.

Exemplo codigo Big-O - O(n):

def sum_array(arr):
    total = 0
    for i in arr:
        total += i
    return total

complexidade-big-o

Exemplo codigo Big-O - O(1):

def sum_first_two(arr):
    if len(arr) >= 2:
        return arr[0] + arr[1]
    else:
        return None

complexidade-big-o

Exemplo codigo Big-O - O(log n):

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low+high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

complexidade-big-o

Exemplo codigo Big-O - O(n^2):

def sum_square_matrix(matrix):
    n = len(matrix)
    total = 0
    for i in range(n):
        for j in range(n):
            total += matrix[i][j]
    return total

complexidade-big-o

Exemplo codigo Big-O - O(n^3):

def multiply_matrices(A, B):
    n = len(A)
    C = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

complexidade-big-o

Exemplo codigo Big-O - O(2^n):

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

complexidade-big-o

Exemplo codigo Big-O - O(n!):

def permutations(arr):
    if len(arr) == 0:
        return [[]]
    else:
        total = []
        for i in range(len(arr)):
            remaining_elements = arr[:i] + arr[i+1:]
            sub_permutations = permutations(remaining_elements)
            for permutation in sub_permutations:
                total.append([arr[i]] + permutation)
        return total

complexidade-big-o

12 - Vamos falar sobre P e NP?

P e NP são classes de problemas em teoria da computação. Problemas em P podem ser resolvidos em tempo polinomial, enquanto problemas em NP podem ser verificados em tempo polinomial. A questão P = NP é uma das perguntas mais importantes em ciência da computação.

Exemplo codigo O(n^2) P:

def is_valid_solution(board):
    # verify that each row, column, and 3x3 square contains the numbers 1-9
    for row in range(9):
        used_nums = set()
        for col in range(9):
            num = board[row][col]
            if num in used_nums:
                return False
            if num != 0:
                used_nums.add(num)

    # verify that each column contains the numbers 1-9
    for col in range(9):
        used_nums = set()
        for row in range(9):
            num = board[row][col]
            if num in used_nums:
                return False
            if num != 0:
                used_nums.add(num)

    # verify that each 3x3 square contains the numbers 1-9
    for i in range(3):
        for j in range(3):
            used_nums = set()
            for row in range(3):
                for col in range(3):
                    num = board[3*i + row][3*j + col]
                    if num in used_nums:
                        return False
                    if num != 0:
                        used_nums.add(num)
    return True

13 - Vamos falar sobre complexidade assintotica?

A complexidade assintótica descreve o comportamento do algoritmo quando a entrada aumenta para um tamanho infinito. Ela é representada por Big-O e é uma forma de descrever a complexidade de um algoritmo sem se preocupar com constantes e termos de baixa ordem.

Complexidade assintotica eh descrita por Big-O

Exemplo codigo O(n):

def find_min_max(arr):
  n = len(arr)
  min_val = max_val = arr[0]
  for i in range(1, n):
    if arr[i] < min_val:
      min_val = arr[i]
    if arr[i] > max_val:
      max_val = arr[i]
  return min_val, max_val
def best_min_max(arr):
  n = len(arr)
  min_val = arr[0]
  for i in range(1, n):
    if arr[i] < min_val:
      min_val = arr[i]

  for i in range(1, n):
    if arr[i] > min_val:
      max_val = arr[i]

  return min_val, max_val
def find_min(arr):
  n = len(arr)
  min_val = arr[0]
  for i in range(1, n):
    if arr[i] < min_val:
      min_val = arr[i]
  return min_val

def find_max(arr):
  n = len(arr)
  max_val = arr[0]
  for i in range(1, n):
    if arr[i] > max_val:
      max_val = arr[i]
  return max_val

def find_min_max_best(arr):
  return find_min(arr), find_max(arr)

complexidade-assintotica

14 - Vamos falar sobre escalabilidade?

A escalabilidade descreve a capacidade de um sistema de lidar com um aumento na carga de trabalho. Isso pode ser medido em termos de desempenho, tempo de resposta ou tempo de execução. A escalabilidade é importante para garantir que um sistema possa lidar com um aumento na carga de trabalho sem degradar o desempenho.

Duas perspectivas de escalabilidade:

  1. Requisicoes com "entradas maiores"

  2. Mais requisicoes

escalabilidade

Eventualmente uma saida "boa o suficiente", produzida em um tempo menor eh preferivel a saida "perfeita", produzida em mais tempo.

escalabilidade-2

Exemplo codigo O(n):

def insert_sorted(arr, n):
  i = len(arr) - 1
  arr.append(n)
  while i >= 0 and arr[i] > n:
    arr[i + 1] = arr[i]
    i -= 1
  arr[i + 1] = n
  return arr

A insercao em uma AVL acontece em O(log n)

Bancos de dados utilizam uma estrutura de dados chamada B-tree para indices.

15 - Como determinar a complexidade de um algoritmo?

Existem várias técnicas para determinar a complexidade de um algoritmo, incluindo análise de tempo, análise de espaço e análise assintótica. A análise assintótica, representada por Big-O, é uma forma de descrever a complexidade de um algoritmo sem se preocupar com constantes e termos de baixa ordem. Ela é a técnica mais comum e útil para determinar a complexidade de um algoritmo.

Qual eh o impacto do auemnto de carga de trabalho no tempo de execucao do meu codigo?

Como determinar a complexidade da busca de "maior valor"?

def find_max(numbers):
  max_number = numbers[0]
  for number in numbers:
    if number > max_number:
      max_number = number
  return max_number

complexidade-algoritmo

complexidade-algoritmo-2

complexidade-algoritmo-3

16 - Como determinar a complexidade do BubbleSort?

O BubbleSort é um algoritmo de ordenação que percorre uma lista várias vezes. Em cada iteração, ele compara pares de elementos adjacentes e os troca se estiverem na ordem errada. O algoritmo continua até que a lista esteja ordenada.

def bubble_sort(arr):
  n = len(arr)
  for i in range(n):
    for j in range(n - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
  return arr

bubble-sort

Releases

No releases published

Packages

No packages published