1 of 21

מרתון מבוא למדעי המחשב ב��סיבוכיות זמן ריצה

בס"ד

צביקה ברגר

2 of 21

סיבוכיות - שיטת האב

​

​

  • כעת נסתכל על הפונקציה :

​

​

בס"ד

3 of 21

סיבוכיות – 2021 מועד א

בס"ד

4 of 21

סיבוכיות – 2021 מועד א

בס"ד

5 of 21

סיבוכיות – 2021 מועד א

בס"ד

6 of 21

סיבוכיות – 2021 מועד א

בס"ד

7 of 21

סיבוכיות – 2021 מועד א

בס"ד

8 of 21

סיבוכיות – 2021 מועד א

בס"ד

n^2 log(n)

1. n^3

2. n^2 log(n)

3. n^3

4. n^2

9 of 21

סיבוכיות – 2021 מועד א

בס"ד

n^2 log(n)

10 of 21

סיבוכיות – 2021 מועד א

בס"ד

T(n) = T(n-c) + T(c)

= T(n-2c) + 2T(c)

= T(n-3c) + 3T(c)

.

.

.

= (n/c)T(c) = O(n)

11 of 21

סיבוכיות – 2020 מועד א

בס"ד

12 of 21

סיבוכיות – 2020 מועד א

בס"ד

13 of 21

סיבוכיות – 2020 מועד א

בס"ד

14 of 21

סיבוכיות – 2020 מועד א

בס"ד

15 of 21

סיבוכיות – 2020 מועד א

בס"ד

16 of 21

סיבוכיות – 2020 מועד א

בס"ד

17 of 21

סיבוכיות – 2019 מועד א

בס"ד

18 of 21

סיבוכיות – 2016 מועד א

בס"ד

19 of 21

סיבוכיות – 2015 מועד א

בס"ד

20 of 21

סיבוכיות – 2019 מועד ב

בס"ד

21 of 21

שאלות?

בס"ד