Czy w tym przypadku złożoność algorytmu jest liniowa, jak kilka razy wykonam tę pętle?
for(int i = 0; i < 4; i++)
{
// cos robi
if(i == 3) { i = 0;}
// jesli cos to przerywa petle if(cos) break;
}
Czy w tym przypadku złożoność algorytmu jest liniowa, jak kilka razy wykonam tę pętle?
for(int i = 0; i < 4; i++)
{
// cos robi
if(i == 3) { i = 0;}
// jesli cos to przerywa petle if(cos) break;
}
Nie, pokazany kawałek kodu ma złożoność stałą O(1) bo ilość obrotów pętli nie zależy od danych.
edit: oczywiście z tym ifem z d**y to jest nieskończona pętla, a w ogóle przekręcanie licznika pętli w trakcie iteracji to nigdy nie jest dobry pomysł...
Nie, pokazany kawałek kodu to nieskończona pętla.
czemu nieskończona pętla jak jest podany if, który przerywa pętlę instrukcją break? Ten if zawsze się kiedyś w pewnym momencie się wykona.
O RLY? Bo my tego drugiego ifa nie widzimy.
for(int i = 0; i < n; i++)
{
// cos robi
if(i == (n - 1)) { i = 0;}
// jesli cos to przerywa petle if(cos) break; // ten if zawsze sie wykona
}
if(i == (n - 1)) { i = 0;}
tutaj przeciez zeruje wartosc i wiec ta petla bedzie caly czas sie wykonywac...
Ale mam jeszcze taki warunek:
if(cos) break;
np.Jak jakaś zmienna z zewnątrz osiągnie jakoś wartość to wywołujemy instrukcję break.
No to złożoność zależy od tego twojego cos
, od niczego innego.
int zmienna = 0;
int n;
cin >> n;
int *tablica = new int [n]
for(int i = 0; i < n; i++)
{
if(i == (n - 1)) { i = 0;}
if(zmienna == 15) break;
++zmienna;
}
To jaka tutaj złożoność by była?
O(1), bo wciąż nic nie zależy od rozmiaru danych wejściowych.
O(1) co oznacza?
Poczytaj o notacji wielkiego O (Big O notation).
int k = 0;
for(int i = 0; i < n; i++)
{
k =k + i;
if(i == (n - 1)) { i = 0;}
if(k == 15) break;
}
Wtedy też O(1)?
Zakładając, że k to dana wejściowa
Dane wejściowe pobieranie są od użytkownika...
Chyba, że masz na myśli takie coś:
int main(int argc,char** argv){
int k = parseInt(argv[1]);
k = 0;
for(int i = 0; i < n; i++)
{
k =k + i;
if(i == (n - 1)) { i = 0;}
if(k == 15) break;
}
return 0;
}
Ale to nie zmienia faktu, że złożoność nadal O(1) bo co nie dasz za k pętla wykona się taką samą ilość razy.
Chociaż trochę przekłamuję co to jest dana wejściowa
Ech, rząd złożoności obliczeniowej mówi jak zmienia się czas wykonania kodu w zależności od zmian w rozmiarze danych wejściowych. To znaczy że jeśli program dla pewnych danych X wykonuje sie Y sekund to chcemy wiedzieć jak dlugo będzie sie wykonywał dla danych rozmiaru n*X.
Twoje pętle NIE ZALEŻĄ nijak od rozmiaru danych wejściowych więc ZAWSZE wykonują się tyle samo razy. Cały czas pokazujesz pętle które wykonają się 15 razy!
Rząd liniowy -> O(n), o który pytałeś, oznaczałby że zmiana rozmiaru danych 10 razy spowodowałaby 10 krotny wzrost czasu wykonania programu, a u ciebie wcale tak nie będzie.
Nie jestem autorem tematu, tylko chciałem się dopytać korzystając z okazji :)
int main() {
int n = 0;
int suma = 0;;
cin >> n;
for (int i=1; i <= n; i++){
suma+=i;
}
cout << suma;
return 0;
}
To już ma notacje O(n) czy się myle? :)
Tak