Złożoności obliczeniowe Kamillo: Złożoność Obliczeniowa − Informatyka Algorytmy Wiem że na tym forum jest sporo osób z Informatyki, a mam pytanie z podstaw więc raczej się ktoś znajdzie do pomocy Mam zadanie posortować złożoności obliczeniowe od najwolniej do najszybciej rosnącej. I tu mam pytanie: Szybciej rosnąca będzie O(n²) czy O(n)? Wiem, że O(n²) jest słabszą złożonością ale nie wiem czy słabszy = wolniejszy czy jak.

Pytający: Dla n=k: O(n)=O(k) O(n²)=O(k²) Dla n=2k: O(n)=O(2k) O(n²)=O(4k²) I która złożoność rośnie szybciej wraz ze zwiększaniem rozmiaru danych wejściowych?

Kamillo: Na pierwszy rzut oka widzę, że złożoność O(n²) rośnie szybciej... Ale pozostaje mi niepewność czy jeśli złożoność szybciej rośnie to czy algorytm działający z taką złożonością będzie działał też szybciej czy to jest działa wtedy na odwrót? Szybciej rosnąca złożoność = szybsze działanie algorytmu?

Mariusz: Szybciej rosnąca złożoność wolniejsze działanie algorytmu Dla małego rozmiaru danych pewien wpływ na szybkość działania może mieć stała ukryta w notacji O

Kamillo: O właśnie tak mi się wydawało. Bardzo wam dziękuję!

Mariusz: https://ideone.com/96VYTE Pobaw się tymi algorytmami a sprawdzisz jak to ze złożonością Możesz dopisać sobie zliczanie porównań i przestawień elementów